  Classic symmetry-breaking problems on graphs have gained a lot of attention
in models of modern parallel computation. The Adaptive Massively Parallel
Computation (AMPC) is a model that captures the central challenges in data
center computations. Chang et al. [PODC'2019] gave an extremely fast, constant
time, algorithm for the $(\Delta + 1)$-coloring problem, where $\Delta$ is the
maximum degree of an input graph of $n$ nodes. The algorithm works in the most
restrictive low-space setting, where each machine has $n^{\delta}$ local space
for a constant $0 < \delta < 1$.
  In this work, we study the vertex-coloring problem in sparse graphs
parameterized by their arboricity $\alpha$, a standard measure for sparsity. We
give deterministic algorithms that in constant, or almost constant, time give
$\text{poly} ~\alpha$ and $O(\alpha)$-colorings, where $\alpha$ can be
arbitrarily smaller than $\Delta$. A strong and standard approach to compute
arboricity-dependent colorings is through the Nash-Williams forest
decomposition, which gives rise to an (acyclic) orientation of the edges such
that each node has a small out-degree.
  Our main technical contribution is giving efficient deterministic algorithms
to compute these orientations and showing how to leverage them to find
colorings in low-space AMPC. A key technical challenge is that the color of a
node may depend on almost all of the other nodes in the graph and these
dependencies cannot be stored on a single machine. Nevertheless, our novel and
careful exploration technique yields the orientation, and the
arboricity-dependent coloring, with a sublinear number of adaptive queries per
node.
