Distributed Lovász Local Lemma under Bandwidth Limitations

2024/05/12 by Halldórsson, Magnús M., Maus, Yannic, Peltonen, Saku · 2 citations
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2405.07353

Abstract

The constructive Lovász Local Lemma has become a central tool for designing efficient distributed algorithms. While it has been extensively studied in the classic LOCAL model that uses unlimited bandwidth, much less is known in the bandwidth-restricted CONGEST model. In this paper, we present bandwidth- and time-efficient algorithms for various subclasses of LLL problems, including a large class of subgraph sampling problems that are naturally formulated as LLLs. Lastly, we use our LLLs to design efficient CONGEST algorithms for coloring sparse and triangle-free graphs with few colors. These coloring algorithms are exponentially faster than previous LOCAL model algorithms.

Cited by

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

Related

• Distributed Delta-Coloring under Bandwidth Limitations
• Sublogarithmic Distributed Algorithms for Lov 'asz Local lemma, and the\n Complexity Hierarchy
• Efficient CONGEST Algorithms for the Lovasz Local Lemma
• The randomized local computation complexity of the Lovász local lemma
• Overcoming Congestion in Distributed Coloring