LLL for k-SAT k-CNF of max degree d Theorem d≤2k-2 > 3 satisfying assignment for uniform random assignment X1,X2,...,Xn for clause Ci,bad event Ai:Ci is not satisfied LLL: e(d+1)≤2kE >0Theorem d  2k￾2 ∃ satisfying assignment for φ e(d + 1)  2k for clause Ci , bad event Ai : uniform random assignment X1, X2,...,Xn Ci is not satisfied φ : k-CNF of max degree d LLL: Pr￾ ⇤ n i=1 Ai ⇥ > 0 LLL for k-SAT