Satisfiability threshold for random regular \textsc{nae-sat}

DOI10.1007/S00220-015-2492-8zbMath1335.68243OpenAlexW2287686747MaRDI QIDQ5963757

Jian Ding, Nike Sun, Allan Sly

Publication date: 23 February 2016

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

Full work available at URL: https://doi.org/10.1007/s00220-015-2492-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Classical equilibrium statistical mechanics (general) (82B05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (20)

Information-theoretic thresholds from the cavity method ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Free energy subadditivity for symmetric random Hamiltonians ⋮ Lower bounds on the chromatic number of random graphs ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ Combinatorial statistics and the sciences ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Local minima in disordered mean-field ferromagnets ⋮ Critical window of the symmetric perceptron ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Charting the replica symmetric phase ⋮ The satisfiability threshold for random linear equations ⋮ Spin systems on Bethe lattices ⋮ Unnamed Item ⋮ The number of solutions for random regular NAE-SAT ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• Recurrence of distributional limits of finite planar graphs
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• An elementary proof of the local central limit theorem
• Maximum independent sets on random regular graphs
• Processes on unimodular random networks
• The scaling window of the 2-SAT transition
• Constraint satisfaction: random regular k-SAT
• Survey propagation as local equilibrium equations
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• A new look at survey propagation and its generalizations
• Information, Physics, and Computation
• Almost all cubic graphs are Hamiltonian
• Approximating the unsatisfiability threshold of random formulas
• Almost all regular graphs are hamiltonian
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The asymptotic k-SAT threshold
• Satisfiability threshold for random regular NAE-SAT
• Survey propagation: An algorithm for satisfiability
• Determining computational complexity from characteristic ‘phase transitions’
• The Satisfiability Threshold fork-XORSAT
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Catching the k-NAESAT threshold
• Going after the k-SAT threshold
• Bicolouring random hypergraphs
• The condensation transition in random hypergraph 2-coloring
• Random 2-SAT: Results and problems

This page was built for publication: Satisfiability threshold for random regular \textsc{nae-sat}