A Lower Bound for the Distributed Lov\'asz Local Lemma

Autor:	Brandt, Sebastian, Fischer, Orr, Hirvonen, Juho, Keller, Barbara, Lempiäinen, Tuomo, Rybicki, Joel, Suomela, Jukka, Uitto, Jara
Rok vydání:	2015
Předmět:	Computer Science - Distributed Parallel and Cluster Computing Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	We show that any randomised Monte Carlo distributed algorithm for the Lov\'asz 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\'asz 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]. Comment: 17 pages, 3 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1511.00900 Zobrazit plný text záznamu View this record from Arxiv