%0 Journal Article %A Coja-Oghlan, Amin %A Frieze, Alan %D 2014 %T Analyzing Walksat on Random Formulas %U https://kilthub.cmu.edu/articles/journal_contribution/Analyzing_Walksat_on_Random_Formulas/6476846 %R 10.1184/R1/6476846.v1 %2 https://kilthub.cmu.edu/ndownloader/files/11908310 %K random structures %K phase transitions %K k-SAT %K local search algorithms %X

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).

%I Carnegie Mellon University