License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.31
URN: urn:nbn:de:0030-drops-148333
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14833/
Go to the corresponding LIPIcs Volume Portal

Maus, Yannic ; Uitto, Jara

Efficient CONGEST Algorithms for the Lovász Local Lemma

pdf-format:
LIPIcs-DISC-2021-31.pdf (0.8 MB)

Abstract

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

@InProceedings{maus_et_al:LIPIcs.DISC.2021.31,
  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 =		{https://drops.dagstuhl.de/opus/volltexte/2021/14833},
  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
Collection: 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