Skip to main content
Browse by:
GROUP

Replica Symmetry Breaking for Random Regular NAESAT

Departmental Colloquium
Thursday, October 15, 2020
3:15 pm - 4:15 pm
Allan Sly (Princeton, Math)

Ideas from physics have predicted a number of important properties of sparse random constraint satisfaction problems such as the satisfiability threshold and the free energy (the exponential growth rate of the number of solutions). Another prediction is the condensation regime where most of the solutions are contained in a small number of clusters and the overlap of two random solutions is concentrated on two points. We establish this phenomenon for the first time in the random regular NAESAT model.