A better algorithm for random k-SAT

Abstract

Let F 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 F with high probability for constraint densities m/n<(1-eps_k)2^k\ln(k)/k, where eps_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, J. of Algorithms 1996].

References in corpus (5)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Survey propagation: an algorithm for satisfiability
• Typical random 3-SAT formulae and the satisfiability threshold
• The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT

Cited by in corpus (20)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The asymptotic $k$-SAT threshold
• Catching the k-NAESAT Threshold
• Walksat stalls well below the satisfiability threshold
• Going after the k-SAT Threshold
• Biased landscapes for random Constraint Satisfaction Problems
• The large deviations of the whitening process in random constraint satisfaction problems
• The set of solutions of random XORSAT formulae
• Analyzing Walksat on random formulas
• On the concentration of the number of solutions of random satisfiability formulas
• The decimation process in random k-SAT
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Aspects of Statistical Physics in Computational Complexity
• Super Strong ETH is False for Random $k$-SAT
• Inside the clustering threshold for random linear equations
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Inside the clustering window for random linear equations
• Structure of random r-SAT below the pure literal threshold
• Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test
• Random hypergraphs and property B