Shared randomness helps with local distributed problems

DOI10.4230/LIPICS.ICALP.2025.16MaRDI QIDQ7346446zbMATH OpenFDO

Authors Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, Jara Uitto

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.16

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A lower bound for the distributed Lovász local lemma
• A time hierarchy theorem for the LOCAL model
• Almost global problems in the LOCAL model
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Classification of distributed binary labeling problems
• Communication Complexity
• Coordination Through Shared Randomness
• Distributed Computing: A Locality-Sensitive Approach
• Distributed degree splitting, edge coloring, and orientations
• Distributed graph problems through an automata-theoretic lens
• Finitely dependent coloring
• Finitely dependent cycle coloring
• How much does randomness help with locally checkable problems?
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• scientific article; zbMATH DE number 7765409 (Why is no real title available?)
• Improved distributed degree splitting and edge coloring
• Landscape of Locality (Invited Talk).
• LCL problems on grids
• Locality in Distributed Graph Algorithms
• Locality in online, dynamic, sequential, and distributed graph algorithms
• Locally checkable labelings with small messages
• Locally checkable problems in rooted trees
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• New classes of distributed time complexity
• On derandomizing local distributed algorithms
• On the complexity of local distributed graph problems
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Quantum advantage for the LOCAL model in distributed computing
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• Symmetrization for finitely dependent colouring
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• Trade-offs in distributed interactive proofs
• What Can be Computed Locally?
• What Can Be Observed Locally?

Cited in

(1)

• Shared randomness in locally checkable problems: the role of computational assumptions

This page was built for publication: Shared randomness helps with local distributed problems

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