Brief Announcement : Distributed Derandomization Revisited

Sameep Dahal, Francesco d'Amore, Henrik Lievonen, Timothe Picavet, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

17 Downloads (Pure)

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.
Original languageEnglish
Title of host publication37th International Symposium on Distributed Computing (DISC 2023)
EditorsRotem Oshman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Chapter40
Pages1-5
Number of pages5
ISBN (Electronic)978-3-95977-301-0
DOIs
Publication statusPublished - Oct 2023
MoE publication typeA4 Conference publication
EventInternational Symposium on Distributed Computing - L'Aquila, Italy
Duration: 10 Oct 202312 Oct 2023
Conference number: 37

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume281
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
Country/TerritoryItaly
CityL'Aquila
Period10/10/202312/10/2023

Fingerprint

Dive into the research topics of 'Brief Announcement : Distributed Derandomization Revisited'. Together they form a unique fingerprint.

Cite this