## 6 The Algorithmic Lovasz Local Lemma  
The original LLL (Lemma 1) and its variants presented in Section 4 are all _existence theorems:_ they prove that there exists a realization that satisfies each of \(\overline{A}_{1}\ldots\overline{A}_{n}\), but do not tell anything about how to find such a realization algorithmically. In many cases, it is very natural to look for an algorithmic solution. For example, in the case presented in Example 3 (see Section 5.2), we have shown that in a \(k\)-CNF formula \(\Phi\), if every clause overlaps with at most \(2^{k-2}\) other clauses, then \(\Phi\) is satisfiable. In most applications, however, it is not enough just to know that a formula is satisfiable, we also want to find an actual satisfying truth assignment. The original LLL, as applied to this problem, does not provide it. A naive approach would be to try rejection sampling to solve the above problem: repeatedly pick random truth assignments until one of them eventually satisfies all clauses. Since the LLL guarantees \(\Pr(\overline{A}_{1}\ldots\overline{A}_{n})>0\), we must find a satisfying truth assignment after a finite number of trials, with probability 1. Unfortunately, this approach can be very inefficient, because the probability \(\Pr(\overline{A}_{1}\ldots\overline{A}_{n})\), although guaranteed to be positive by the LLL, is typically exponentially small. This would therefore lead to an exponential time algorithm, essentially not better than exhaustive search. The first proof of the possibility of an efficient algorithmic LLL was published by [PERSON] [10] in 1991. His algorithm, however, was somewhat technical, and required a stronger condition on neighborhoods than the original LLL. After a sequence of improvements, the most elegant solution was published by [PERSON] and [PERSON] [11]. It is worth mentioning that the authors received the prestigious _Godel Prize_ in 2020 for this work. The [PERSON] algorithm can be best presented via a formulation called the _variable version_ of the LLL. Let \(X_{1},\ldots,X_{m}\) be mutually independent random variables. Denote the \"bad\" events that we want to avoid by \(A_{1},\ldots,A_{n}\) and let \(p_{i}=\Pr(A_{i})\) be the probability of \(A_{i}\), \(i=1,\ldots,n\). Let \(\operatorname{vbl}(A_{i})\subseteq\{X_{1},\ldots,X_{m}\}\) denote the subset of variables on which \(A_{i}\) depends. In particular, if \(\operatorname{vbl}(A_{i})\cap\operatorname{vbl}(A_{j})=\emptyset\), then \(A_{i}\) and \(A_{j}\) are independent. The dependency graph \(G=(V,E)\) is defined by \(V=\{1,\ldots,n\}\) and \(E=\{(i,j)\mid\operatorname{vbl}(A_{i})\cap\operatorname{vbl}(A_{j})\
eq \emptyset\}\). With the above framework, the Moser-Tardos algorithm is surprisingly simple and elegant, see Algorithm 1. We present the most concise version, found in [PERSON] [12]. The correctness and complexity of the algorithm is captured by the following theorem, which implies that this is a probabilistic polynomial time algorithm. **Theorem 7**. : _If the conditions of the asymmetric LLL hold, i.e., there are real numbers \(x_{1},\ldots,x_{n}\in[0,1)\), such that_  
\[p_{i}\;\leq\;x_{i}\prod_{(i,j)\in E}(1-x_{j})\;\;\;\;\;(\forall i)\,,\]  
_then the algorithm resamples each \(\operatorname{vbl}(A_{i})\) at most an expected number of \(\frac{x_{i}}{1-x_{i}}\) times before finding an assignment that satisfies all the \(\overline{A}_{i}\). Therefore, the expected overall number of resamplings is at most \(\sum_{i=1}^{n}\frac{x_{i}}{1-x_{i}}\)._  
_Furthermore, if the maximum degree of the dependency graph is \(D\), and \(p_{i}\leq\frac{1}{\operatorname{e}(D+1)}\;\;(\forall i)\) holds, then \(\operatorname{vbl}(A_{i})\) is resampled at most an expected number of \(1/D\) times, and the total expected number of resamplings is bounded by \(n/D\)._  
While the algorithm itself is surprisingly straightforward and elegant, the proof of the above Theorem is far from simple, see [PERSON] and [PERSON] [11].