Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2021/14833/
Maus, Yannic ; Uitto, Jara
Efficient CONGEST Algorithms for the Lovász Local Lemma
| pdf-format: |
|
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 | |
| Seminar: | 35th International Symposium on Distributed Computing (DISC 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 04.10.2021 |
