Lovasz Local Lemma (LLL) Variables take independent random values X1,X2,...,X ·Violation Probability:each c∈C is violated with prob.≤p Dependency Degree:each c e C shares variables with s D other constraints c'∈C,i.e.vbl(c)nvbl(c)≠⑦ LLL [Erdos,Lovasz,1975]: epD≤I→solution exists .Constructive LLL [Moser,Tardos,2010]: epD≤I→solution can be found very efficiently• Variables take independent random values • Violation Probability: each is violated with prob. ≤ p • Dependency Degree: each shares variables with ≤ D other constraints , i.e. • LLL [Erdős, Lovász, 1975]: ⟹ solution exists • Constructive LLL [Moser, Tardos, 2010]: ⟹ solution can be found very efficiently X1, X2,…, Xn c ∈ C c ∈ C c′∈ C 𝗏𝖻𝗅(c) ∩ 𝗏𝖻𝗅(c′) ≠ ∅ epD ≤ 1 epD ≤ 1 Lovász Local Lemma (LLL)