The Satisfiability Threshold of Random 3-SAT Is at Least 3.52

Abstract

We prove that a random 3-SAT instance with clause-to-variable density less than 3.52 is satisfiable with high probability. The proof comes through an algorithm which selects (and sets) a variable depending on its degree and that of its complement.

References in corpus (2)

• The Scaling Window of the 2-SAT Transition
• The Asymptotic Order of the k-SAT Threshold

Cited by in corpus (7)

• A better algorithm for random k-SAT
• A Quantum Lovasz Local Lemma
• On belief propagation guided decimation for random k-SAT
• The Satisfiability Threshold for Non-Uniform Random 2-SAT
• On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
• A Model of Random Industrial SAT
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem