Sameep Dahal · Francesco d'Amore · Henrik Lievonen · Timothé Picavet · Jukka Suomela

Brief announcement: Distributed derandomization revisited

DISC 2023 · 37th International Symposium on Distributed Computing, L’Aquila, Italy, October 2023 · doi:10.4230/LIPIcs.DISC.2023.40

authors’ version publisher’s version arXiv.org

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.

Publication

Rotem Oshman (Ed.): 37th International Symposium on Distributed Computing (DISC 2023), volume 281 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:5, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023

ISBN 978-3-95977-301-0

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.