One-step replica symmetry breaking of random regular NAE-SAT I

Danny Nam, Allan Sly, Youngtak Sohn

In a broad class of sparse random constraint satisfaction problems(CSP), deep heuristics from statistical physics predict that there is a condensation phase transition before the s…