Mathematics Colloquium

Time and Location:

Speaker:

Link:

We will describe recent progress in determination of asymptotic behavior in random constraint satisfaction problems, including the independent set problem on random graphs, random regular NAE-SAT, and random SAT. The results include sharp phase transitions and some understanding of solution geometry. In this lecture we will survey the physics heuristics, then go over some of the mathematical approaches to the study of random CSPs, particularly involving the moment method. Implementing the moment method often reduces to the solution of difficult (non-convex) optimization problems; and we will discuss one basic strategy that has been used to solve some of these problems, which is to (1) use "a priori" estimates to localize the optimization to a small neighborhood, and (2) use the contractivity of tree recursions and a "local update" procedure to solve the optimization within the small neighborhood.
Based on joint works with Zsolt Bartha, Jian Ding, Allan Sly, and Yumeng Zhang.