Hardness of Minimal Symmetry Breaking in Distributed Computing

DOI10.1145/3293611.3331605MaRDI QIDQ5145237zbMATH OpenOpenAlexWikidataFDO

Authors Alkida Balliu, Juho Hirvonen, Dennis Olivetti, Jukka Suomela

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/1811.01643

zbMATH Keywords

graph algorithmslocal modeldistributed complexity theorylocally checkable labelings

Mathematics Subject Classification ID

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

Recommendations

• On the Complexity of Distributed Splitting Problems
• Locality of not-so-weak coloring
• Polynomial lower bound for distributed graph coloring in a weak LOCAL model
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• On the complexity of distributed graph coloring

Cited in

(6)

• The complexity landscape of distributed locally checkable problems on trees
• Completing the node-averaged complexity landscape of LCLs on trees
• Classification of distributed binary labeling problems
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• Distributed Lower Bounds for Ruling Sets
• scientific article; zbMATH DE number 5010828 (Why is no real title available?)

This page was built for publication: Hardness of Minimal Symmetry Breaking in Distributed Computing

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