STOC 2018 · 50th ACM Symposium on Theory of Computing, Los Angeles, CA, USA, June 2018 · doi:10.1145/3188745.3188860

A number of recent papers – e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) – have advanced our understanding of one of the most fundamental questions in theory of distributed computing: what are the possible time complexity classes of LCL problems in the LOCAL model? In essence, we have a graph problem $\Pi$ in which a solution can be *verified* by checking all radius-$O(1)$ neighbourhoods, and the question is what is the smallest $T$ such that a solution can be *computed* so that each node chooses its own output based on its radius-$T$ neighbourhood. Here $T$ is the distributed time complexity of $\Pi$.

The time complexity classes for deterministic algorithms in bounded-degree graphs that are known to exist by prior work are $\Theta(1)$, $\Theta(\log^* n)$, $\Theta(\log n)$, $\Theta(n^{1/k})$, and $\Theta(n)$. It is also known that there are two gaps: one between $\omega(1)$ and $o(\log \log^* n)$, and another between $\omega(\log^* n)$ and $o(\log n)$. It has been conjectured that many more gaps exist, and that the overall time hierarchy is relatively simple – indeed, this is known to be the case in restricted graph families such as cycles and grids.

We show that the picture is much more diverse than previously expected. We present a general technique for engineering LCL problems with numerous different deterministic time complexities, including $\Theta( \log^{\alpha} n )$ for any $\alpha \ge 1$, $2^{\Theta( \log^{\alpha} n )}$ for any $\alpha \le 1$, and $\Theta(n^{\alpha})$ for any $\alpha < 1/2$ in the high end of the complexity spectrum, and $\Theta( \log^{\alpha} \log^* n )$ for any $\alpha \ge 1$, $\smash{2^{\Theta( \log^{\alpha} \log^* n )}}$ for any $\alpha \le 1$, and $\Theta((\log^* n)^{\alpha})$ for any $\alpha \le 1$ in the low end of the complexity spectrum; here $\alpha$ is a positive rational number.

Ilias Diakonikolas, David Kempe, and Monika Henzinger (Eds.): *STOC’18, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, pages 1307–1318, ACM Press, New York, 2018

ISBN 978-1-4503-5559-9