Going after the k-SAT threshold

DOI10.1145/2488608.2488698zbMATH Open1293.68164arXiv1212.1682OpenAlexW3105248014MaRDI QIDQ5495841FDOQ5495841

Authors: Amin Coja-Oghlan, Konstantinos Panagiotou 

Publication date: 7 August 2014

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

Abstract: Random $k$-SAT is the single most intensely studied example of a random constraint satisfaction problem. But despite substantial progress over the past decade, the threshold for the existence of satisfying assignments is not known precisely for any $kgeq3$. The best current results, based on the second moment method, yield upper and lower bounds that differ by an additive $kcdotfracln22$, a term that is unbounded in $k$ (Achlioptas, Peres: STOC 2003). The basic reason for this gap is the inherent asymmetry of the Boolean value `true' and `false' in contrast to the perfect symmetry, e.g., among the various colors in a graph coloring problem. Here we develop a new asymmetric second moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This technique enables us to compute the $k$-SAT threshold up to an additive $ln2-frac12+O(1/k)approx0.19$. Independently of the rigorous work, physicists have developed a sophisticated but non-rigorous technique called the "cavity method" for the study of random CSPs (M'ezard, Parisi, Zecchina: Science 2002). Our result matches the best bound that can be obtained from the so-called "replica symmetric" version of the cavity method, and indeed our proof directly harnesses parts of the physics calculations.

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

Recommendations

• The asymptotic \(k\)-SAT threshold
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• The asymptotic \(k\)-SAT threshold
• Proof of the satisfiability conjecture for large \(k\)
• Threshold values of random K‐SAT from the cavity method

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)

Cited In (20)

• Statistical limits of spiked tensor models
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems
• Optimal testing for planted satisfiability problems
• Phase transitions in discrete structures
• Planting colourings silently
• Satisfiability threshold for random regular \textsc{nae-sat}
• Generalised and quotient models for random and/or~trees and application to satisfiability
• Critical window of the symmetric perceptron
• Biased random k‐SAT
• The asymptotic \(k\)-SAT threshold
• The asymptotic \(k\)-SAT threshold
• Unsatisfiability bounds for random CSPs from an energetic interpolation method
• The number of satisfying assignments of random regular \(k\)-SAT formulas
• Proof of the satisfiability conjecture for large \(k\)
• Catching the \(k\)-NAESAT threshold
• Minimal contagious sets in random regular graphs
• Random instances of problems in NP -- algorithms and statistical physics
• Ultrametricity in spin glasses
• Satisfiability threshold for power law random 2-SAT in configuration model

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495841)