  In this work, we develop the low-space Massively Parallel Computation (MPC)
complexity landscape for a family of fundamental graph problems on trees. We
present a general method that solves most locally checkable labeling (LCL)
problems exponentially faster in the low-space MPC model than in the LOCAL
message passing model. In particular, we show that all solvable LCL problems on
trees can be solved in $O(\log n)$ time (high-complexity regime) and that all
LCL problems on trees with deterministic complexity $n^{o(1)}$ in the LOCAL
model can be solved in $O(\log \log n)$ time (mid-complexity regime). We
observe that obtaining a greater speed-up than from $n^{o(1)}$ to $\Theta(\log
\log n)$ is conditionally impossible, since the problem of 3-coloring trees,
which is a LCL problem with LOCAL time complexity $n^{o(1)}$, has a conditional
MPC lower bound of $\Omega(\log \log n)$ [Linial, FOCS'87; Ghaffari, Kuhn and
Uitto, FOCS'19]. We emphasize that we solve LCL problems on constant-degree
trees, and that our algorithms are deterministic, component-stable, and work in
the low-space MPC model, where local memory is $O(n^\delta)$ for $\delta \in
(0,1)$ and global memory is $O(m)$.
  For the high-complexity regime, there are two key ingredients. One is a novel
$O(\log n)$-time tree rooting algorithm, which may be of independent interest.
The other is a novel pointer-chain technique and analysis that allows us to
solve any solvable LCL problem on trees in $O(\log n)$ time. For the
mid-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who
gave a canonical LOCAL algorithm for solving LCL problems on trees.
