A Better Algorithm for Random k-SAT

Let *** be a uniformly distributed random k -SAT formula with n variables and m clauses. We present a polynomial time algorithm that finds a satisfying assignment of *** with high probability for constraint densities $m/n , where *** k ***0. Previously no efficient algorithm was known to find solutions with non-vanishing probability beyond m /n = 1.817·2 k /k [Frieze and Suen, Journal of Algorithms 1996].

• Publication year

  2009

• Venue

  SIAM journal on computing (Print)

• Publication date

  2009-02-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/09076516XarXiv 0902.3583
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A machine program for theorem-proving

  2011cited by this paper
• On smoothed k-CNF formulas and the Walksat algorithm

  2009cited by this paper
• Algorithmic Barriers from Phase Transitions

  2008cited by this paper
• Poisson Cloning Model for Random Graphs

  2008cited by this paper
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT

  2008cited by this paper
• The Threshold for Random kSAT is 2 k ( ln 2 + o ( 1 ) )

  2007cited by this paper
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation

  2007influential reference
• Gibbs states and the set of solutions of random constraint satisfaction problems

  2006cited by this paper
• The probabilistic analysis of a greedy satisfiability algorithm

  2006cited by this paper
• Random graphs

  2006influential reference
• Survey propagation: An algorithm for satisfiability

  2005cited by this paper
• THE THRESHOLD FOR RANDOM k-SAT IS 2 log 2−O(k)

  2004cited by this paper
• The threshold for random k-SAT is 2^k log 2 - O(k)

  2004cited by this paper
• Poisson Cloning Model for Random Graph

  2004cited by this paper
• Exponential bounds for DPLL below the satisfiability threshold

  2004cited by this paper
• The Threshold for Random k-SAT is 2^k ln2 - O(k)

  2003cited by this paper
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold

  2003cited by this paper
• The satisfiability threshold for random 3-SAT is at least 3.52

  2003cited by this paper
• A Study of Pure Random Walk on Random Satisfiability Problems with "Physical" Methods

  2003cited by this paper
• Survey propagation: An algorithm for satisfiability

  2002influential reference
• The probabilistic analysis of a greedy satisfiability algorithm

  2002cited by this paper
• BerkMin: A fast and robust SAT-solver

  2002cited by this paper
• Typical random 3-SAT formulae and the satisfiability threshold

  2000influential reference
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• Analysis of Two Simple Heuristics on a Random Instance of k-SAT

  1996influential reference
• Mick gets some (the odds are on his side) (satisfiability)

  1992cited by this paper
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem

  1990cited by this paper

• The random k-SAT Gibbs uniqueness threshold revisited

  2025influential citation
• Algorithmic thresholds in combinatorial optimization depend on the time scaling

  2025cites this paper
• Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm

  2025cites this paper
• Belief Propagation Guided Decimation on Random k-XORSAT

  2025cites this paper
• Strong Low Degree Hardness for Stable Local Optima in Spin Glasses

  2025cites this paper
• Temporal Exploration of Random Spanning Tree Models

  2025cites this paper
• WalkSAT is linear on random 2-SAT

  2024cites this paper
• Limits of Sequential Local Algorithms on the Random k-XORSAT Problem

  2024cites this paper
• Optimization of random cost functions and statistical physics

  2024cites this paper
• Learning Hard-Constrained Models with One Sample

  2023cites this paper
• Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT

  2023cites this paper
• Improved Bounds for Sampling Solutions of Random CNF Formulas

  2022cites this paper
• Fast sampling of satisfying assignments from random k-SAT

  2022cites this paper
• The overlap gap property: A topological barrier to optimizing over random structures

  2021cites this paper
• Satisfiability and Algorithms for Non-uniform Random k-SAT

  2021cites this paper
• The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

  2021influential citation
• Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses

  2021cites this paper
• Results on a Super Strong Exponential Time Hypothesis

  2020influential citation
• Belief Propagation on the random k-SAT model

  2020cites this paper
• Random hypergraphs and property B

  2020cites this paper
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion

  2020cites this paper
• Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model

  2019cites this paper
• EUCLIDEAN CORRELATIONS IN COMBINATORIAL OPTIMIZATION PROBLEMS: A STATISTICAL PHYSICS APPROACH

  2019cites this paper
• Faster Random k-CNF Satisfiability

  2019cites this paper
• On Super Strong ETH

  2019cites this paper
• Counting solutions to random CNF formulas

  2019influential citation
• Super Strong ETH is False for Random k-SAT

  2018cites this paper
• Encoding of Spatially Coupled LDGM Codes for Lossy Source Compression

  2018cites this paper
• The Freezing Threshold for k-Colourings of a Random Graph

  2018cites this paper
• P ≠ Np

  2018cites this paper
• Biased landscapes for random constraint satisfaction problems

  2018cites this paper
• Belief Propagation Guided Decimation Fails on Random Formulas

  2017influential citation
• Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem

  2017cites this paper
• Walksat Stalls Well Below Satisfiability

  2016cites this paper
• The large deviations of the whitening process in random constraint satisfaction problems

  2016cites this paper
• Analysing Survey Propagation Guided Decimation on Random Formulas

  2016cites this paper
• Resolution Complexity of Random Constraint Satisfaction Problems

  2016cites this paper
• Inside the clustering window for random linear equations

  2015cites this paper
• Random Instances of Problems in NP - Algorithms and Statistical Physics

  2015cites this paper
• Proof of the Satisfiability Conjecture for Large k

  2014cites this paper
• Aspects of Statistical Physics in Computational Complexity

  2014cites this paper
• Structure vs Combinatorics in Computational Complexity

  2014cites this paper
• Sets that are connected in two random graphs

  2014cites this paper
• S tructure vs C ombinatorics in C omputational C omplexity

  2014cites this paper
• The asymptotic k-SAT threshold

  2014cites this paper
• Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem

  2014cites this paper
• Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees

  2014cites this paper
• Random Structures and Algorithms

  2014influential citation
• On the Complexity of Random Satisfiability Problems with Planted Solutions

  2013cites this paper
• Inside the clustering threshold for random linear equations

  2013cites this paper
• Sharp thresholds and the partition function

  2013cites this paper
• The asymptotic k-SAT threshold

  2013cites this paper
• Exact algorithms for constraint satisfaction problems

  2013cites this paper
• The freezing threshold for k-colourings of a random graph

  2012influential citation
• Going after the k-SAT threshold

  2012cites this paper
• Frozen variables in random boolean constraint satisfaction problems

  2012cites this paper
• Satisfiability-based Set Membership Filters

  2012cites this paper
• The set of solutions of random XORSAT formulae

  2011cites this paper
• Catching the k-NAESAT threshold

  2011influential citation
• An algorithm for random signed 3-SAT with intervals

  2011cites this paper
• Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test

  2011cites this paper
• The Decimation Process in Random k-SAT

  2011cites this paper
• Analyzing Walksat on Random Formulas

  2011cites this paper
• On belief propagation guided decimation for random k-SAT

  2010cites this paper
• Structure of random r-SAT below the pure literal threshold

  2010cites this paper
• On the concentration of the number of solutions of random satisfiability formulas

  2010cites this paper
• Random Constraint Satisfaction Problems

  2009cites this paper