2026-07-23T08:16:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19166 2024-03-06T11:03:35Z ddc:004 open_access

Brief Announcement: Distributed Derandomization Revisited Dahal, Sameep d'Amore, Francesco Lievonen, Henrik Picavet, Timothé Suomela, Jukka Distributed algorithm Derandomization LOCAL model 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sameep Dahal and Francesco d'Amore and Henrik Lievonen and Timothé Picavet and Jukka Suomela 2023 Is Part Of LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2023.40 urn:nbn:de:0030-drops-191660 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.40 eng https://creativecommons.org/licenses/by/4.0/legalcode