Replica symmetry breaking for random regular NAE-SAT

Abstract:   In a wide class of random constraint satisfaction problems, ideas from statistical physics predict that there is a rich set of phase transitions governed by one-step replica symmetry breaking (1RSB). In particular, it is conjectured that there is a condensation regime below the satisfiability threshold, where the solution space condenses into large clusters. We establish this phenomenon for the random regular NAE-SAT model by showing that most of the solutions lie in a bounded number of clusters and the overlap of two independent solutions concentrates on two points. Central to the proof is to calculate the moments of the number of clusters whose size is in an O(1) window.

This is joint work with Danny Nam and Allan Sly.