Resume
Research
Learning
Blog
Teaching
Jokes
Kernel Papers

# 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)}$