file.pdf (279.64 kB)
Download file

Analyzing Walksat on Random Formulas

Download (279.64 kB)
journal contribution
posted on 16.05.2014, 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).

History

Date

16/05/2014

Usage metrics

Exports