Zsolt Bartha

Replica Symmetry Breaking in the Random Regular k-NAE-SAT Problem

Abstract: For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs. For random k-SAT and related models it happens at constraint density alpha ~ 2^k. Just below the threshold, further results suggest that the solution space has a “one-step replica symmetry breaking” (1RSB) structure of a large bounded number of near-orthogonal clusters inside {0,1}^N. In the unsatisfiable regime, it is natural to consider the problem of max-satisfiability: violating the least number of constraints. Recent works suggest that for alpha very large, the max-sat value approaches the mean-field limit, which conjecturally has a “fullRSB” structure. Studying how one phase transitions into the other, in this work we show that in the random regular k-NAE-SAT model the 1RSB description breaks down already above alpha ~ 4^k/k^3, the so-called Gardner transition established by physicists.

This is joint work with Nike Sun and Yumeng Zhang.