Analyzing Walksat on Random Formulas
Amin Coja-Oghlan, ALAN M. FRIEZE · SIAM Journal on Computing · 2014
Let $\mathbf{\Phi}$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. We prove that the \tt Walksat algorithm from Papadimitriou [On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1991, pp. 163--169] and Schöning [A probabilistic algorithm for $k$-SAT and constraint satisfaction problems, in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 410--414] finds a satisfying assignment of $\mathbf{\Phi}$ in polynomial time with high probability if $m/n\leq\rho\cdot2^k/k$ for a certain constant $\rho>0$. This is an improvement by a factor of $\Theta(k)$ over the best previous analysis of \tt Walksat from Coja-Oghlan et al. [On smoothed $k$-CNF formulas and the Walksat algorithm, in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2009, pp. 451--460].