MIT Probability Seminar
Monday, May 03, 2021 at 4:15pm to 5:15pmVirtual Event
Title: 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 the condensation regime below the satisfiability threshold, where the solution space condenses into the 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.