Lovasz local lemma and the resampling algorithm
Kent Quanrud · 75:24
The lecture proves the algorithmic Lovász Local Lemma: if each bad event is rare enough relative to its local dependency degree (for \(k\)-SAT, each clause intersects at most about \(2^k/e\) others), a satisfying assi...