Efficient CONGEST Algorithms for the Lovasz Local Lemma
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2021
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
19
Series
35th International Symposium on Distributed Computing, DISC 2021, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 209
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.Description
| openaire: EC/H2020/755839/EU//BANDWIDTH
Keywords
Other note
Citation
Maus, Y & Uitto, J 2021, Efficient CONGEST Algorithms for the Lovasz Local Lemma . in S Gilbert (ed.), 35th International Symposium on Distributed Computing, DISC 2021 ., 31, Leibniz International Proceedings in Informatics, LIPIcs, vol. 209, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Freiburg, Germany, 04/10/2021 . https://doi.org/10.4230/LIPIcs.DISC.2021.31