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

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