Sebastian Brandt · Orr Fischer · Juho Hirvonen · Barbara Keller · Tuomo Lempiäinen · Joel Rybicki · Jukka Suomela · Jara Uitto

A lower bound for the distributed Lovász local lemma

STOC 2016 · 48th ACM Symposium on Theory of Computing, Cambridge, MA, USA, June 2016 · doi:10.1145/2897518.2897570

authors’ version publisher’s version arXiv.org

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^* 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

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.