  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 of $\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 LCL 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.
