  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\ge1$, $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; here
$\alpha$ is a positive rational number.
