A spectral technique for random satisfiable 3CNF formulas

Let I be a random 3CNF formula generated by choosing a truth assignment ϕ for variables x 1 , x n uniformly at random and including every clause with i literals set true by ϕ with probability p i , independently. We show that for any constants 0 ≤ η 2 ,η 3 ≤ 1 there is a constant d min so that for all d ≥ d min a spectral algorithm similar to the graph coloring algorithm of Alon and Kahale will find a satisfying assignment with high probability for p 1 = d / n 2 , p 2 = η 2 d / n 2 , and p 3 = η 3 d / n 2 . Appropriately setting the η i 's yields natural distributions on satisfiable 3CNFs, not‐all‐equal‐sat 3CNFs, and exactly‐one‐sat 3CNFs. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008