Efficient CONGEST Algorithms for the Lovasz Local Lemma

DOI10.4230/LIPICS.DISC.2021.31MaRDI QIDQ6083398zbMATH OpenOpenAlexFDO

Authors Yannic Maus, Jara Uitto

Publication date 8 December 2023

Full work available at URL https://arxiv.org/abs/2108.02638

zbMATH Keywords

CONGESTdistributed graph algorithmslocally checkable labelingsLovász local lemma

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: We present a poly $loglogn$ time randomized CONGEST algorithm for a natural class of Lovasz Local Lemma (LLL) instances on constant degree graphs. This implies, among other things, that there are no LCL problems with randomized complexity between $logn$ and poly $loglogn$. Furthermore, we provide extensions to the network decomposition algorithms given in the recent breakthrough by Rozhon and Ghaffari [STOC2020] and the follow up by Ghaffari, Grunau, and Rozhon [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.

Cited in

(2)

• New algorithmic aspects of the local lemma with applications to routing and partitioning
• Distributed symmetry breaking on power graphs via sparsification

This page was built for publication: Efficient CONGEST Algorithms for the Lovasz Local Lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083398)