Breaking of 1RSB in random MAX-NAE-SAT

Zsolt Bartha, Nike Sun, Yumeng Zhang

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 a…