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

DOI10.1145/3293611.3331636MaRDI QIDQ5145239zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

distributed graph algorithms

Mathematics Subject Classification ID

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

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

Cited in

(4)

• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
• Classification of distributed binary labeling problems
• 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)