Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Maus, Yannic; Uitto, Jara License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-148333


Efficient CONGEST Algorithms for the Lovász Local Lemma



We present a poly log log n time randomized CONGEST algorithm for a natural class of Lovász Local Lemma (LLL) instances on constant degree graphs. This implies, among other things, that there are no LCL problems with randomized complexity between Ω(log n) and poly log log n. Furthermore, we provide extensions to the network decomposition algorithms given in the recent breakthrough by Rozhoň and Ghaffari [STOC2020] and the follow up by Ghaffari, Grunau, and Rozhoň [SODA2021]. In particular, we show how to obtain a large distance separated weak network decomposition with a negligible dependency on the range of unique identifiers.

BibTeX - Entry

  author =	{Maus, Yannic and Uitto, Jara},
  title =	{{Efficient CONGEST Algorithms for the Lov\'{a}sz Local Lemma}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-148333},
  doi =		{10.4230/LIPIcs.DISC.2021.31},
  annote =	{Keywords: distributed graph algorithms, CONGEST, Lov\'{a}sz Local Lemma, locally checkable labelings}

Keywords: distributed graph algorithms, CONGEST, Lovász Local Lemma, locally checkable labelings
Seminar: 35th International Symposium on Distributed Computing (DISC 2021)
Issue date: 2021
Date of publication: 04.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI