Phase transitions in random constraint satisfaction problems

Neyman Seminar
Sep 13, 2017 4:00pm to 5:00pm
1011 Evans Hall
Happening As Scheduled
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...
Nike Sun, University of California, Berkeley