LIPIcs.DISC.2023.40.pdf
- Filesize: 0.54 MB
- 5 pages
Document
Brief Announcement: Distributed Derandomization Revisited
Authors
Sameep Dahal 
,
Francesco d'Amore ,
Henrik Lievonen ,
Timothé Picavet ,
Jukka Suomela
-
Part of:
Volume:
37th International Symposium on Distributed Computing (DISC 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-10-05
File
Document Identifiers
Author Details
Acknowledgements
We thank the participants in our reading group at Aalto University for helpful discussions.
Cite AsGet BibTex
Sameep Dahal, Francesco d'Amore, Henrik Lievonen, Timothé Picavet, and Jukka Suomela. Brief Announcement: Distributed Derandomization Revisited. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 40:1-40:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.DISC.2023.40
https://doi.org/10.4230/LIPIcs.DISC.2023.40
Abstract
One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves a locally checkable labeling problem (LCL) can be derandomized with at most exponential overhead. The original proof assumes that the number of random bits is bounded by some function of the input size. We give a new, simple proof that does not make any such assumptions - it holds even if the randomized algorithm uses infinitely many bits. While at it, we also broaden the scope of the result so that it is directly applicable far beyond LCL problems.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
- Theory of computation → Pseudorandomness and derandomization
Keywords
- Distributed algorithm
- Derandomization
- LOCAL model
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the local model. SIAM Journal on Computing, 48(1):122-143, 2019. URL: https://doi.org/10.1137/17M1117537.
- Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. URL: https://doi.org/10.1137/0221015.
- Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. URL: https://doi.org/10.1137/S0097539793254571.
- David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. URL: https://doi.org/10.1137/1.9780898719772.
- Jukka Suomela. Landscape of locality (invited talk). In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), 2020. URL: https://doi.org/10.4230/LIPIcs.SWAT.2020.2.