Phase transitions in random constraint satisfaction problems
Seminar | September 13 | 4-5 p.m. | 1011 Evans Hall
Nike Sun, University of California, Berkeley
We will discuss a class of random constraint satisfaction problems (CSPs), including the boolean k-satisfiability (k-SAT) problem. For numerous random CSP models, heuristic methods from statistical physics yield detailed predictions on phase transitions and other phenomena. We will survey some of these 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.