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

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