Catching the k-NAESAT Threshold

Abstract

The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems ('CSPs') mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. According to deep but non-rigorous arguments from statistical mechanics, this discrepancy is due to a change in the geometry of the set of solutions called condensation that occurs shortly before the actual threshold for the existence of solutions (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007). To cope with condensation, physicists have developed a sophisticated but non-rigorous formalism called Survey Propagation (Mezard, Parisi, Zecchina: Science 2002). This formalism yields precise conjectures on the threshold values of many random CSPs. Here we develop a new Survey Propagation inspired second moment method for the random k-NAESAT problem, which is one of the standard benchmark problems in the theory of random CSPs. This new technique allows us to overcome the barrier posed by condensation rigorously. We prove that the threshold for the existence of solutions in random $k$-NAESAT is $2^{k-1}\ln2-(\frac{\ln2}2+\frac14)+\eps_k$, where $|\eps_k| \le 2^{-(1-o_k(1))k}$, thereby verifying the statistical mechanics conjecture for this problem.

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Random subcubes as a toy model for constraint satisfaction problems
• The Satisfiability Threshold for k-XORSAT

Cited by in corpus (15)

• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• The asymptotic $k$-SAT threshold
• Going after the k-SAT Threshold
• Biased landscapes for random Constraint Satisfaction Problems
• Phase transitions in the $q$-coloring of random hypergraphs
• The large deviations of the whitening process in random constraint satisfaction problems
• Spin systems on Bethe lattices
• The replica symmetric phase of random constraint satisfaction problems
• Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
• Breaking of 1RSB in random MAX-NAE-SAT
• Inside the clustering threshold for random linear equations
• Inside the clustering window for random linear equations
• Coloring Random Non-Uniform Bipartite Hypergraphs
• Random hypergraphs and property B
• Non-orderability of random triangular groups by using random 3CNF formulas