The condensation phase transition in the regular $k$-SAT model

DOI10.4230/LIPIcs.APPROX-RANDOM.2016.22zbMath1398.68213arXiv1507.03512OpenAlexW2963248366MaRDI QIDQ4636454

Victor Bapst, Amin Coja-Oghlan

Publication date: 19 April 2018

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

zbMATH Keywords

phase transitionscondensationbelief propagationrandom \(k\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Applications of branching processes (60J85) Phase transitions (general) in equilibrium statistical mechanics (82B26) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (9)

Phase transitions in discrete structures ⋮ The Number of Satisfying Assignments of Random Regulark-SAT Formulas ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Harnessing the Bethe free energy ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Unnamed Item ⋮ On the Potts antiferromagnet on random graphs ⋮ The number of solutions for random regular NAE-SAT ⋮ Belief propagation on the random \(k\)-SAT model

This page was built for publication: The condensation phase transition in the regular $k$-SAT model