Going after the k-SAT threshold

DOI10.1145/2488608.2488698zbMath1293.68164arXiv1212.1682OpenAlexW3105248014MaRDI QIDQ5495841

Amin Coja-Oghlan, Konstantinos D. Panagiotou

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionsrandom structuressecond moment methodbelief propagation\(k\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

The Number of Satisfying Assignments of Random Regulark-SAT Formulas ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Statistical limits of spiked tensor models ⋮ Ultrametricity in spin glasses ⋮ The asymptotic \(k\)-SAT threshold ⋮ Planting Colourings Silently ⋮ \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ Optimal testing for planted satisfiability problems ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ Phase Transitions in Discrete Structures ⋮ Minimal contagious sets in random regular graphs

This page was built for publication: Going after the k-SAT threshold