Phase transitions in random constraint satisfaction problems

Seminar | September 13 | 4-5 p.m. | 1011 Evans Hall

 Nike Sun, University of California, Berkeley

 Department of Statistics

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.

 510- 642-2781