Algorithmic Lovász local lemma

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. The absence of a feature is considered a bad event and if it can be shown that all such bad events can be avoided simultaneously with non-zero probability, the existence follows. The lemma itself reads as follows:

Let ${\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}$ be a finite set of events in the probability space Ω. For ${\displaystyle A\in {\mathcal {A}}}$ let ${\displaystyle \Gamma (A)}$ denote a subset of ${\displaystyle {\mathcal {A}}}$ such that ${\displaystyle A}$ is independent from the collection of events ${\displaystyle {\mathcal {A}}\setminus (\{A\}\cup \Gamma (A))}$. If there exists an assignment of reals ${\displaystyle x:{\mathcal {A}}\rightarrow (0,1)}$ to the events such that

${\displaystyle \forall A\in {\mathcal {A}}:\Pr[A]\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

then the probability of avoiding all events in ${\displaystyle {\mathcal {A}}}$ is positive, in particular

${\displaystyle \Pr \left[\,{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\,\right]\geq \prod _{A\in {\mathcal {A}}}(1-x(A)).}$

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

${\displaystyle \Pr \left[{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right]}$

is only bounded by a product of small numbers

${\displaystyle \prod _{A\in {\mathcal {A}}}(1-x(A))}$

and therefore likely to be very small.

Under the assumption that all of the events in ${\displaystyle {\mathcal {A}}}$ are determined by a finite collection of mutually independent random variables ${\displaystyle {\mathcal {P}}}$ in Ω, Robin Moser and Gábor Tardos proposed an efficient randomized algorithm that computes an assignment to the random variables in ${\displaystyle {\mathcal {P}}}$ such that all events in ${\displaystyle {\mathcal {A}}}$ are avoided.

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.

The following example illustrates how the algorithmic version of the Lovász Local Lemma can be applied to a simple problem.

Let Φ be a CNF formula over variables X₁, ..., X_n, containing n clauses, and with at least k literals in each clause, and with each variable X_i appearing in at most ${\displaystyle {\frac {2^{k}}{ke}}}$ clauses. Then, Φ is satisfiable.

This statement can be proven easily using the symmetric version of the Algorithmic Lovász Local Lemma. Let X₁, ..., X_n be the set of mutually independent random variables ${\displaystyle {\mathcal {P}}}$ which are sampled uniformly at random.

Firstly, we truncate each clause in Φ to contain exactly k literals. Since each clause is a disjunction, this does not harm satisfiability, for if we can find a satisfying assignment for the truncated formula, it can easily be extended to a satisfying assignment for the original formula by reinserting the truncated literals.

Now, define a bad event A_j for each clause in Φ, where A_j is the event that clause j in Φ is unsatisfied by the current assignment. Since each clause contains k literals (and therefore k variables) and since all variables are sampled uniformly at random, we can bound the probability of each bad event by

${\displaystyle \Pr[A_{j}]=p=2^{-k}.}$

Since each variable can appear in at most ${\displaystyle {\frac {2^{k}}{ke}}}$ clauses and there are k variables in each clause, each bad event A_j can depend on at most

${\displaystyle D=k\left({\frac {2^{k}}{ke}}-1\right)\leq {\frac {2^{k}}{e}}-1}$

other events. Therefore:

${\displaystyle D+1\leq {\frac {2^{k}}{e}},}$

multiplying both sides by ep we get:

${\displaystyle ep(D+1)\leq e2^{-k}{\frac {2^{k}}{e}}=1}$

it follows by the symmetric Lovász Local Lemma that the probability of a random assignment to X₁, ..., X_n satisfying all clauses in Φ is non-zero and hence such an assignment must exist.

Now, the Algorithmic Lovász Local Lemma actually allows us to efficiently compute such an assignment by applying the algorithm described above. The algorithm proceeds as follows:

It starts with a random truth value assignment to the variables X₁, ..., X_n sampled uniformly at random. 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. Hence, the Algorithmic Lovász Local Lemma proves that this algorithm has an expected runtime of at most

${\displaystyle {\frac {n}{{\frac {2^{k}}{e}}-k}}}$

steps on CNF formulas that satisfy the two conditions above. 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. The main difference is that in WalkSAT, after the unsatisfied clause C is selected, a single variable in C is selected at random and has its value flipped (which can be viewed as selecting uniformly among only ${\displaystyle k}$ rather than all ${\displaystyle 2^{k}}$ value assignments to C).

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:

• Probabilistic proofs of non-probabilistic theorems
• Random graph

The algorithm described above lends itself well to parallelization, since resampling two independent events ${\displaystyle A,B\in {\mathcal {A}}}$, i.e. ${\displaystyle {\text{vbl}}(A)\cap {\text{vbl}}(B)=\emptyset }$, in parallel is equivalent to resampling A, B sequentially. Hence, at each iteration of the main loop one can determine the maximal set of independent and satisfied events S and resample all events in S in parallel.

Under the assumption that the assignment function x satisfies the slightly stronger conditions:

${\displaystyle \forall A\in {\mathcal {A}}:\Pr[A]\leq (1-\varepsilon )x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

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

${\displaystyle O\left({\frac {1}{\varepsilon }}\log \sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}\right)}$

steps before it terminates. The parallel version of the algorithm can be seen as a special case of the sequential algorithm shown above, and so this result also holds for the sequential case.