A Lower Bound for the Distributed Lovász Local Lemma

Abstract

We show that any randomised Monte Carlo distributed algorithm for the Lovász 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 Lovász 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 }^{\ast }n)$ rounds [Chung et al. 2014].

17 pages, 3 figures

References in corpus (1)

• A constructive proof of the general Lovasz Local Lemma

Cited by in corpus (2)

• LCL problems on grids
• Constant Space and Non-Constant Time in Distributed Computing