Phase transitions in random constraint satisfaction problems

Phase transitions in random constraint satisfaction problems

Neyman Seminar
Sep 13, 2017, 04:00 PM - 05:00 PM | 1011 Evans Hall | Happening As Scheduled
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...