In theoretical computer science, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence.
However, the lemma is non-constructive in that it does not provide any insight on how to avoid the bad events.
If the events {A1, ..., An} are determined by a finite collection of mutually independent random variables, a simple Las Vegas algorithm with expected polynomial runtime proposed by Robin Moser and Gábor Tardos[1] can compute an assignment to the random variables such that all events are avoided.
The Lovász Local Lemma is a powerful tool commonly used in the probabilistic method to prove the existence of certain complex mathematical objects with a set of prescribed features.
A typical proof proceeds by operating on the complex object in a random manner and uses the Lovász Local Lemma to bound the probability that any of the features is missing.
is positive, in particular The Lovász Local Lemma is non-constructive because it only allows us to conclude the existence of structural properties or complex objects but does not indicate how these can be found or constructed efficiently in practice.
Note that random sampling from the probability space Ω is likely to be inefficient, since the probability of the event of interest is only bounded by a product of small numbers and therefore likely to be very small.
are determined by a finite collection of mutually independent random variables
Hence, this algorithm can be used to efficiently construct witnesses of complex objects with prescribed features for most problems to which the Lovász Local Lemma applies.
Prior to the recent work of Moser and Tardos, earlier work had also made progress in developing algorithmic versions of the Lovász Local Lemma.
József Beck in 1991 first gave proof that an algorithmic version was possible.
[2] In this breakthrough result, a stricter requirement was imposed upon the problem formulation than in the original non-constructive definition.
we wish to avoid that is determined by a collection of mutually independent random variables
This means that an assignment vP is sampled randomly and independently according to the distribution of the random variable P. The algorithm then enters the main loop which is executed until all events in
are avoided, at which point the algorithm returns the current assignment.
be a finite set of mutually independent random variables in the probability space Ω.
Thus the expected total number of resampling steps and therefore the expected runtime of the algorithm is at most The proof of this theorem using the method of entropy compression can be found in the paper by Moser and Tardos [1] The requirement of an assignment function x satisfying a set of inequalities in the theorem above is complex and not intuitive.
But this requirement can be replaced by three simple conditions: The version of the Lovász Local Lemma with these three conditions instead of the assignment function x is called the Symmetric Lovász Local Lemma.
We can also state the Symmetric Algorithmic Lovász Local Lemma: Let
The following example illustrates how the algorithmic version of the Lovász Local Lemma can be applied to a simple problem.
This statement can be proven easily using the symmetric version of the Algorithmic Lovász Local Lemma.
Therefore: multiplying both sides by ep we get: it follows by the symmetric Lovász Local Lemma that the probability of a random assignment to X1, ..., Xn satisfying all clauses in Φ is non-zero and hence such an assignment must exist.
While there exists a clause in Φ that is unsatisfied, it randomly picks an unsatisfied clause C in Φ and assigns a new truth value to all variables that appear in C chosen uniformly at random.
Once all clauses in Φ are satisfied, the algorithm returns the current assignment.
A stronger version of the above statement is proven by Moser,[3] see also Berman, Karpinski and Scott.
[4] The algorithm is similar to WalkSAT which is used to solve general boolean satisfiability problems.
As mentioned before, the Algorithmic Version of the Lovász Local Lemma applies to most problems for which the general Lovász Local Lemma is used as a proof technique.
Some of these problems are discussed in the following articles: The algorithm described above lends itself well to parallelization, since resampling two independent events
Under the assumption that the assignment function x satisfies the slightly stronger conditions: for some ε > 0 Moser and Tardos proved that the parallel algorithm achieves a better runtime complexity.
In this case, the parallel version of the algorithm takes an expected steps before it terminates.