Analyzing Walksat on random formulas

Abstract

Let F be a uniformly distributed random k-SAT formula with n variables and m clauses. We prove that the Walksat algorithm from Papadimitriou (FOCS 1991)/Schoning (FOCS 1999) finds a satisfying assignment of F in polynomial time w.h.p. if m/n<ρ2^k/k for a certain constant ρ>0. This is an improvement by a factor of $\Theta (k)$ over the best previous analysis of Walksat from Coja-Oghlan, Feige, Frieze, Krivelevich, Vilenchik (SODA 2009).

References in corpus (1)

• A better algorithm for random k-SAT

Cited by in corpus (4)

• Walksat stalls well below the satisfiability threshold
• Biased landscapes for random Constraint Satisfaction Problems
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Using deep learning to construct stochastic local search SAT solvers with performance bounds