Algorithmic Lovasz Local Lemma

The Lovasz Local Lemma (LLL) is an existential argument; specifically, the LLL says that (under appropriate conditions) the probability of avoiding all undesirable events is positive, meaning that such a configuration must exist.

But how does one actually find a configuration that avoids all bad events, efficiently?

Notation

We introduce some notation, along with a concrete example from k-SAT

• $\mathcal{V}$ is a set of variables e.g. the positive and negative literals $X_1, ... X_n$ in k-SAT
• $\mathcal{A} = \{ A_1, ..., A_m \}$ are the “bad” events that are functions of $\mathcal{V}$ e.g. $A_i$ is the event that the $i$th clause is unsatisfiable
• $Vbl(A_i)$ is the (sub)set of $\mathcal{V}$ involved in computing $A_i$ e.g. $Vbl(A_i)$ is the set of all variables involved in the $i$th clause
• $\Gamma(A_i)$ is the set of all $A_j$ such that $Vbl(A_i) \cap Vbl(A_j) \neq \emptyset$ i.e. the interacting variables between $A_i$ and $A_j$ e.g. the set of all $A_j$ such that they share variables with the $i$th clause

Algorithm

Given $\mathcal{V}, \mathcal{A}$, choose a random assignment $\sigma_v$ for each random variable $v \in \mathcal{V}$. While there is some $A_i \in \mathcal{A}$ such that $A(\sigma) = 1$ (i.e. a bad event is happening), (1) Choose an arbitrary event $A_i$ with $A(\sigma) = 1$ and (2) update $\sigma$ by reselecting/resampling $\{\sigma_v : v \in Vbl(A_i) \}$ randomly.

Theorem (Symmetric Algorithmic LLL by Moser-Tardos 2010): Let $\mathcal{A}$ be a collection of bad events determined by random variables in $\mathcal{V}$. Suppose $\forall A \in \mathcal{A}$:

• $\lvert \Gamma(A) \lvert \leq d + 1$ i.e. $A$ is independent of all but $d$ other events
• $\mathbb{P}[A] \leq 1 / e (d+1)$ i.e. the probability of bad event $A$ is relatively small compared to the number of dependencies $d$

Then the given algorithm will find assignments such that no bad event in $\mathcal{A}$ occurs, and the expected number of re-randomizations is $P(\lvert\mathcal{A}\lvert / (d+1))$.

Theorem (Asymmetric Algorithmic LLL): Let $\mathcal{A}$ be a collection of bad events determined by random variables in $\mathcal{V}$. Suppose $\exists x: \mathcal{A} \rightarrow (0, 1)$ such that $\forall A \in \mathcal{A}$:

$$\mathbb{P}[A] \leq x(A) \prod_{B \in \Gamma(A) \setminus \{A \}} (1 - x(B))$$

Then algorithm will find assignment such that no event of $\mathcal{A}$ occurs, and the expected number of rerandomizations is $\leq \sum_{A \in \mathcal{A}} \frac{x(A)}{1 - x(A)}$.

Proof of Symmetric Algorithmic LLL

We can prove the symmetric algorithmic LLL via the asymmetric algorithmic LLL. Set $x(A) = 1/(d+1)$ for all $A \in \mathcal{A}$. Suppose that $\forall A \in \mathcal{A}, \lvert\Gamma(A)\lvert d + 1$ and $\mathbb{P}[A] \leq 1/e(d+1)$. We can bound:

$$x(A) \prod_{B \in \Gamma(A) \setminus \{A \}} (1 - x(B)) \geq \frac{1}{d+1}(1 - \frac{1}{d+1})^d \geq \frac{1}{e(d+1)}$$