A Lower Bound for the Distributed Lovasz Local Lemma

We show that any randomised Monte Carlo distributed algorithm for the Lovasz local lemma requires $Omega(log log n)$ communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of $d = O(1)$, where $d$ is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovasz local lemma with a running time of $O(log n)$ rounds in bounded-degree graphs, and the best lower bound before our work was $Omega(log^* n)$ rounds [Chung et al. 2014].