Plenary talk

Thursday, July 22, 13:30 ~ 14:30 UTC-3

Replica Symmetry Breaking for Sparse Random Constraint Satisfaction Problems

Allan Sly

PrincetonUniversity, United States   -   allansly@princeton.edu

Ideas from physics have predicted a number of important properties of 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 phenomena for the first time in sparse CSPs in the random regular NAESAT model.

Joint work with Danny Nam (Princeton University) and Youngtak Sohn (Stanford University).

View abstract PDF