Alkida Balliu · Sebastian Brandt · Dennis Olivetti · Jukka Suomela

How much does randomness help with locally checkable problems?

PODC 2020 · 39th ACM Symposium on Principles of Distributed Computing, online, August 2020 · doi:10.1145/3382734.3405715

authors’ version publisher’s version


Locally checkable labeling problems (LCLs) are distributed graph problems in which a solution is globally feasible if it is locally feasible in all constant-radius neighborhoods. Vertex colorings, maximal independent sets, and maximal matchings are examples of LCLs.

On the one hand, it is known that some LCLs benefit exponentially from randomness—for example, any deterministic distributed algorithm that finds a sinkless orientation requires $\Theta(\log n)$ rounds in the LOCAL model, while the randomized complexity of the problem is $\Theta(\log \log n)$ rounds. On the other hand, there are also many LCLs in which randomness is useless.

Previously, it was not known if there are any LCLs that benefit from randomness, but only subexponentially. We show that such problems exist: for example, there is an LCL with deterministic complexity $\Theta(\log^2 n)$ rounds and randomized complexity $\Theta(\log n \log \log n)$ rounds.


Yuval Emek and Christian Cachin (Eds.): PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 299–308, ACM Press, New York, 2020

ISBN 978-1-4503-7582-5

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.