Derandomizing the Lovasz Local Lemma more effectively

Understand

The famous Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria.

• Kratochvil et al.
• applied this technique to prove that a k-CNF in which each variable appears at most 2^k/(ek) times is always satisfiable [KST93].
• In a breakthrough paper, Beck found that if we lower the occurrences to O(2^(k/48)/k), then a deterministic polynomial-time algorithm can find a satisfying assignment to such an instance [Bec91].