k-CNF of max degree d with m clauses on n variables Solve() Fix(C) Pick a random assignment replace variables in C with random values; X1,X2,…,X while 3 unsatisfied clause D overlapping with C while 3 unsatisfied clause C Fix(C); Fix(D); ≤n recursion trees total nodes:t total of random bits: n+tk (assigned bits) Observation: Fix(C)is called assignment of C is uniquely determined≤m total # nodes: t Solve(φ) Pick a random assignment x1, x2, ... , xn; while ∃ unsatisfied clause C Fix(C); Fix(C) replace variables in C with random values; while ∃ unsatisfied clause D overlapping with C Fix(D); recursion trees total # of random bits: n+tk (assigned bits) Observation: Fix(C) is called assignment of C is uniquely determined φ : k-CNF of max degree d with m clauses on n variables