Stanford University

Phase transitions in random constraint satisfaction problems

Building 380, Room 380-W
Thursday, May 24, 2018 4:30 PM
Open free to public
Nike Sun

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.