A spectral technique for random satisfiable 3CNF formulas
Abraham D. Flaxman · 2003
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 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 [1] will find a satisfying assignment with high probability for p_1 = d/n², p_2 = ...