Linear upper bounds for random walk on small density random 3-cnf

In memory of Mikhail (Misha) Alekhnovich—friend, colleague and brilliant mind Abstract. We analyze the efficiency of the random walk algorithm on random 3-CNF instances and prove linear upper bounds on the running time of this algorithm for small clause density, less than 1.63. This is the first subexponential upper bound on the running time of a local improvement algorithm on random instances. Our proof introduces a simple, yet powerful tool for analyzing such algorithms, which may be of further use. This object, called a terminator, is a weighted satisfying assignment. We show that any CNF having a good (small weight) terminator is assured to be solved quickly by the random walk algorithm. This raises the natural question of the terminator threshold which is the maximal clause density for which such assignments exist (with high probability). We use the analysis of the pure literal heuristic presented by Broder, Frieze, and Upfal [Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 322–330] and Luby, Mitzenmacher, and Shokrollahi [Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 364–373] and show that for small clause densities good terminators exist. Thus we show that the pure literal threshold (≈1.63) is a lower bound on the terminator threshold. (We conjecture the terminator threshold to be in fact higher.) One nice property of terminators is that they can be found efficiently via linear programming. This makes tractable the future investigation of the terminator threshold and also provides an efficiently computable certificate for short running time of the simple random walk heuristic