Analysis of the Random Walk Algorithm on Random 3-CNFs
Mikhail Alekhnovich, Eli Ben‐Sasson · 2002
We analyze the efficiency of the random walk algorithm on random-CNF instances, and prove the first polynomial time upper bound for small clause density, less than. We complement this by proving exponential lower bounds for the running time of this algorithm on the planted-SAT distribution with large constant clause density. This is the first polynomial upper bound on the running time of a local improvement algorithm on random instances, and conforms with the empirically observed efficiency of these algorithms on random CNFs. 1 1