Analyzing Walksat on Random Formulas
journal contributionposted on 2014-05-16, 00:00 authored by Amin Coja-Oghlan, Alan FriezeAlan Frieze
Let Φ 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 Φ 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 Θ(k) over the best previous analysis of Walksat from Coja-Oghlan, Feige, Frieze, Krivelevich, Vilenchik (SODA 2009).