Efficient CONGEST Algorithms for the Lovasz Local Lemma

2021/08/05 by Maus, Yannic, Uitto, Jara · 2 citations
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2108.02638

Abstract

We present a poly log log n 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 log n and poly log log n. 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 by

• On the Complexity of Distributed Edge Coloring and Orientation Problems
• A Post-Quantum Lower Bound for the Distributed Lovasz Local Lemma.

Related

• The randomized local computation complexity of the Lovász local lemma
• A Lower Bound for the Distributed Lovász Local Lemma
• Distributed Lovász Local Lemma under Bandwidth Limitations
• Sublogarithmic Distributed Algorithms for Lov 'asz Local lemma, and the\n Complexity Hierarchy
• Fast Distributed Vertex Splitting with Applications