LOCAL LLL in $\mathrm{poly}(\log \log n)$ Rounds

Abstract

We provide a $\mathrm{poly}(\log \log n)$-round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion $p{d}^c<1$, for a sufficiently large constant $c$. The best previous general round complexity was $\tilde{O}(\log n)$. The key ingredient is a local reduction that amplifies the LLL probability exponent quadratically, while increasing the dependency radius only by a constant factor.

17 pages