The number of solutions for random regular NAE-SAT
arXiv:1604.08546
Abstract
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.
arXiv commentCorrection added starting on page 73
References in corpus (12)
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Phase Transitions in the Coloring of Random Graphs
- An Extended Variational Principle for the SK Spin-Glass Model
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- The asymptotic -SAT threshold
- On local equilibrium equations for clustering states
- Maximum independent sets on random regular graphs
- Harnessing the Bethe free energy
- Limits of discrete distributions and Gibbs measures on random graphs
- A positive temperature phase transition in random hypergraph 2-coloring
- On the concentration of the number of solutions of random satisfiability formulas