One-step replica symmetry breaking of random regular NAE-SAT. II

DOI10.1007/s00220-023-04868-6arXiv2112.00152MaRDI QIDQ6119424

Youngtak Sohn, Allan Sly, Danny Nam

Publication date: 1 March 2024

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Theory of computing (68Qxx) Equilibrium statistical mechanics (82Bxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper-bounding the \(k\)-colorability threshold by counting covers
• On the chromatic number of random regular graphs
• The asymptotic \(k\)-SAT threshold
• The 3-XORSAT threshold.
• Information-theoretic thresholds from the cavity method
• The satisfiability threshold for random linear equations
• Maximum independent sets on random regular graphs
• The Parisi formula
• The scaling window of the 2-SAT transition
• Proof of the Satisfiability Conjecture for Large k
• The Number of Satisfying Assignments of Random Regulark-SAT Formulas
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Information, Physics, and Computation
• Almost all cubic graphs are Hamiltonian
• Approximating the unsatisfiability threshold of random formulas
• Almost all regular graphs are hamiltonian
• The condensation phase transition in the regular $k$-SAT model
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The SK Model Is Infinite Step Replica Symmetry Breaking at Zero Temperature
• The Satisfiability Threshold fork-XORSAT
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Catching the k-NAESAT threshold
• The condensation transition in random hypergraph 2-coloring
• The two possible values of the chromatic number of a random graph
• Satisfiability threshold for random regular \textsc{nae-sat}
• The condensation phase transition in random graph coloring