How much does randomness help with locally checkable problems?

DOI10.1145/3382734.3405715MaRDI QIDQ5855249zbMATH OpenOpenAlexFDO

Authors Alkida Balliu, Sebastian F. Brandt, Dennis Olivetti, Jukka Suomela

Publication date 15 March 2021

Published in Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

LOCAL modeldistributed computational complexitylocally checkable labeling problems

Mathematics Subject Classification ID

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

Cited in

(9)

• The complexity landscape of distributed locally checkable problems on trees
• Completing the node-averaged complexity landscape of LCLs on trees
• Brief announcement: Local advice and local decompression
• Classification of distributed binary labeling problems
• Distributed graph problems through an automata-theoretic Lens
• Distributed graph problems through an automata-theoretic lens
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Almost global problems in the LOCAL model
• Network Decomposition and Distributed Derandomization (Invited Paper)

This page was built for publication: How much does randomness help with locally checkable problems?

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