The number of solutions for random regular NAE-SAT

DOI10.1007/s00440-021-01029-5zbMath1490.60282arXiv1604.08546OpenAlexW3216803780WikidataQ114229363 ScholiaQ114229363MaRDI QIDQ2073174

Nike Sun, Yumeng Zhang, Allan Sly

Publication date: 27 January 2022

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.08546

zbMATH Keywords

random regular \(k\)-\textsf{NAE-SAT}

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Related Items

Phase Transition for Maximum Not-All-Equal Satisfiability, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results

Cites Work

• A positive temperature phase transition in random hypergraph 2-coloring
• Right-convergence of sparse random graphs
• Reconstruction and estimation in the planted partition model
• The asymptotic \(k\)-SAT threshold
• Belief propagation on replica symmetric random factor graph models
• Information-theoretic thresholds from the cavity method
• Bounds for diluted mean-fields spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• Limits of discrete distributions and Gibbs measures on random graphs
• Maximum independent sets on random regular graphs
• On the concentration of the number of solutions of random satisfiability formulas
• Proof of the Satisfiability Conjecture for Large k
• Harnessing the Bethe free energy
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• A new look at survey propagation and its generalizations
• Information, Physics, and Computation
• The condensation phase transition in the regular $k$-SAT model
• The Sherrington-Kirkpatrick Model
• Community detection thresholds and the weak Ramanujan property
• Satisfiability threshold for random regular NAE-SAT
• Survey propagation: An algorithm for satisfiability
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Catching the k-NAESAT threshold
• Threshold values of random K‐SAT from the cavity method
• The condensation transition in random hypergraph 2-coloring
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• On the solution-space geometry of random constraint satisfaction problems
• On the solution‐space geometry of random constraint satisfaction problems
• Satisfiability threshold for random regular \textsc{nae-sat}
• The condensation phase transition in random graph coloring