| Deterministic Algorithms for the Lovasz Local Lemma (2009) | |||||||||
Abstract | |||||||||
| The Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d | |||||||||
Details der Publikation | |||||||||
| |||||||||