Nike Sun: Phase transitions in random constraint satisfaction problems

Tuesday, December 8, 2020 - 4:00pm to 5:00pm
Zoom Registration Link:
Nike Sun

Abstract: I will survey recent progress in determination of asymptotic behavior for random constraint satisfaction problems, including phase transitions and some understanding of solution geometry. I will discuss (as time permits) two ideas that played an important role in these works: (1) combinatorial models for the solution geometry, and (2) contractivity of tree recursions as a tool for calculating expected partition functions on sparse random graphs. This lecture is based in part on joint works with Zsolt Bartha, Jian Ding, Allan Sly, and Yumeng Zhang.