TY - JOUR

T1 - The number of solutions for random regular NAE-SAT

AU - Sly, Allan

AU - Sun, Nike

AU - Zhang, Yumeng

N1 - Funding Information:
Research supported in part by Allan Sly: NSF DMS-1208338, DMS-1352013, Sloan Fellowship, and Nike Sun: NSFMSPRF.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer-Verlag GmbH, DE part of Springer Nature.

PY - 2022/2

Y1 - 2022/2

N2 - Recent work has made substantial progress in understanding the transitions of random constraint satisfaction problems. In particular, for several of these models, the exact satisfiability threshold has been rigorously determined, confirming predictions of statistical physics. Here we revisit one of these models, random regular k-nae-sat: knowing the satisfiability threshold, it is natural to study, in the satisfiable regime, the number of solutions in a typical instance. We prove here that these solutions have a well-defined free energy (limiting exponential growth rate), with explicit value matching the one-step replica symmetry breaking prediction. The proof develops new techniques for analyzing a certain “survey propagation model” associated to this problem. We believe that these methods may be applicable in a wide class of related problems.

AB - Recent work has made substantial progress in understanding the transitions of random constraint satisfaction problems. In particular, for several of these models, the exact satisfiability threshold has been rigorously determined, confirming predictions of statistical physics. Here we revisit one of these models, random regular k-nae-sat: knowing the satisfiability threshold, it is natural to study, in the satisfiable regime, the number of solutions in a typical instance. We prove here that these solutions have a well-defined free energy (limiting exponential growth rate), with explicit value matching the one-step replica symmetry breaking prediction. The proof develops new techniques for analyzing a certain “survey propagation model” associated to this problem. We believe that these methods may be applicable in a wide class of related problems.

UR - http://www.scopus.com/inward/record.url?scp=85119354014&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85119354014&partnerID=8YFLogxK

U2 - 10.1007/s00440-021-01029-5

DO - 10.1007/s00440-021-01029-5

M3 - Article

AN - SCOPUS:85119354014

SN - 0178-8051

VL - 182

JO - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

IS - 1-2

ER -