Setting 2 Variables at a Time Yields a New Lower Bound for Random 3-SAT

Let X be a set of n Boolean variables and denote by C(X) be the set of all 3-clauses over X, i.e. the set of all 8fn 3 possible disjunctions of three distinct, non-complementary literals of variables in X. Let F(n;m) be a random 3-SAT formula formed by selecting, with replacement, m clauses uniformly at random from C(X) and taking their conjunction. Finally, let us say that a sequence of events En occurs with high probability (w.h.p.) if limn!1 Pr[En] = 1. The satisfiability threshold conjecture asserts that there exists a constant r3 such that F(n; rn) is w.h.p. satisfiable for r < r3 and w.h.p. unsatisfiable for r > r3. Experimental evidence suggests r3  4:2. We prove r3 > 3:145 improving over the previous best lower bound r3 > 3:003 due to Frieze and Suen. For this, we introduce a new satisfiability heuristic and analyze its performance. The framework we develop for the analysis of our heuristic allows us to recover most of the previous lower bounds along with our new bound in a uniform manner and with little additional effort.