  We give a randomized $\Delta$-coloring algorithm in the LOCAL model that runs
in $\text{poly} \log \log n$ rounds, where $n$ is the number of nodes of the
input graph and $\Delta$ is its maximum degree. This means that randomized
$\Delta$-coloring is a rare distributed coloring problem with an upper and
lower bound in the same ballpark, $\text{poly}\log\log n$, given the known
$\Omega(\log_\Delta\log n)$ lower bound [Brandt et al., STOC '16].
  Our main technical contribution is a constant time reduction to a constant
number of $(\text{deg}+1)$-list coloring instances, for $\Delta = \omega(\log^4
n)$, resulting in a $\text{poly} \log\log n$-round CONGEST algorithm for such
graphs. This reduction is of independent interest for other settings, including
providing a new proof of Brooks' theorem for high degree graphs, and leading to
a constant-round Congested Clique algorithm in such graphs.
  When $\Delta=\omega(\log^{21} n)$, our algorithm even runs in $O(\log^* n)$
rounds, showing that the base in the $\Omega(\log_\Delta\log n)$ lower bound is
unavoidable.
  Previously, the best LOCAL algorithm for all considered settings used a
logarithmic number of rounds. Our result is the first CONGEST algorithm for
$\Delta$-coloring non-constant degree graphs.
