STOC Conference 2016 Conference Paper
A lower bound for the distributed Lovász local lemma
- Sebastian Brandt 0002
- Orr Fischer
- Juho Hirvonen
- Barbara Keller
- Tuomo Lempiäinen
- Joel Rybicki
- Jukka Suomela
- Jara Uitto
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* n) rounds [Chung et al. 2014].