Nike Sun: Phase transitions in random constraint satisfaction problems

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.