Probability Seminar

Phase transitions in random constraint satisfaction problems.


Speaker(s): Nike Sun (MIT)
I will survey recent progress in determination of asymptotic behavior for random constraint satisfaction problems, including phase transitions and some understanding of solution geometry, particularly in the setting of the random regular NAE-SAT problem. I will discuss (as time permits) two ideas that played important roles in results obtained so far: (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.