# Almost global problems in the LOCAL model

DISC 2018 · 32nd International Symposium on Distributed Computing, New Orleans, USA, October 2018 ·

# Abstract

The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally checkable problems (LCLs) in bounded-degree graphs, the following picture emerges:

• There are lots of problems with time complexities $\Theta(\log^* n)$ or $\Theta(\log n)$.
• It is not possible to have a problem with complexity between $\omega(\log^* n)$ and $o(\log n)$.
• In general graphs, we can construct LCL problems with infinitely many complexities between $\omega(\log n)$ and $n^{o(1)}$.
• In trees, problems with such complexities do not exist.

However, the high end of the complexity spectrum was left open by prior work. In general graphs there are problems with complexities of the form $\Theta(n^\alpha)$ for any rational $0 < \alpha \le 1/2$, while for trees only complexities of the form $\Theta(n^{1/k})$ are known. No LCL problem with complexity between $\omega(\sqrt{n})$ and $o(n)$ is known, and neither are there results that would show that such problems do not exist. We show that:

• In general graphs, we can construct LCL problems with infinitely many complexities between $\omega(\sqrt{n})$ and $o(n)$.
• In trees, problems with such complexities do not exist.

Put otherwise, we show that any LCL with a complexity $o(n)$ can be solved in time $O(\sqrt{n})$ in trees, while the same is not true in general graphs.

# Publication

Ulrich Schmid and Josef Widder (Eds.): 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:16, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018

ISBN 978-3-95977-092-7

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.