Mathematics Colloquium

---

Phase Transitions in Random Constraint Satisfaction Problems

Speaker: Allan Sly, Princeton University

Location: Warren Weaver Hall 1302

Date: Monday, April 17, 2017, 3:45 p.m.

Synopsis:

I will discuss a class of random constraint satisfaction problems (CSPs), examples of which include random colourings of random graphs and the boolean k-satisfiability (k-SAT) problem. For many random CSP models, heuristic methods from statistical physics yield detailed predictions on phase transitions and other phenomena including a sharp threshold in satisfiability. I will survey some of these heuristics and describe recent progress in the development of mathematical theory for these models.

Based on joint work with Jian Ding, Nike Sun and Yumeng Zhang.