Phase transitions in random constraint satisfaction problems

Assistant Professor Nike Sun will discuss random constraint satisfaction problems (CSPs). Broadly, these are large systems of variables subject to randomly generated constraints. Examples include random graph coloring problems and the random k-SAT problem. For a broad class of random CSP models, heuristic methods from statistical physics yield detailed predictions on a rich set of phase transitions and other phenomena, reminiscent of behaviors seen in models of spin glasses or disordered magnets. I will survey some of the physics predictions, and describe some progress in the development of mathematical theory for these models.

This talk is based on joint works with Jian Ding, Allan Sly, and Yumeng Zhang.