Abstract

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

Publication

Daniel Wichs and Yishay Mansour (Eds.): STOC’16, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 479–488, ACM Press, New York, 2016

ISBN 978-1-4503-4132-5

Links

• presentation, 20 June 2016
• presentation at the Helsinki Algorithms Seminar, 3 December 2015
• presentation at the Helsinki Algorithms Seminar, 18 February 2016