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

distributed computational complexityLOCAL modellocally checkable labeling problems

Mathematics Subject Classification ID

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

Cited in

(10)

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

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)