A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma

DOI10.1145/3293611.3331636OpenAlexW2964307896WikidataQ130866480 ScholiaQ130866480MaRDI QIDQ5145239FDOQ5145239

Authors: Sebastian F. Brandt, Yannic Maus, Jara Uitto 

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

Recommendations

• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed algorithms for the Lovász local lemma and graph coloring
• A lower bound for the distributed Lovász local lemma
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• Moser and tardos meet Lovász

zbMATH Keywords

distributed graph algorithms

Mathematics Subject Classification ID

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

Cited In (4)

• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Classification of distributed binary labeling problems
• Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
• Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022

This page was built for publication: A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma

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