  By prior work, we have many results related to distributed graph algorithms
for problems that can be defined with local constraints; the formal framework
used in prior work is locally checkable labeling problems (LCLs), introduced by
Naor and Stockmeyer in the 1990s. It is known, for example, that if we have a
deterministic algorithm that solves an LCL in $o(\log n)$ rounds, we can speed
it up to $O(\log^*n)$ rounds, and if we have a randomized $O(\log^*n)$ rounds
algorithm, we can derandomize it for free.
  It is also known that randomness helps with some LCL problems: there are LCL
problems with randomized complexity $\Theta(\log\log n)$ and deterministic
complexity $\Theta(\log n)$. However, so far there have not been any LCL
problems in which the use of shared randomness has been necessary; in all prior
algorithms it has been enough that the nodes have access to their own private
sources of randomness.
  Could it be the case that shared randomness never helps with LCLs? Could we
have a general technique that takes any distributed graph algorithm for any LCL
that uses shared randomness, and turns it into an equally fast algorithm where
private randomness is enough?
  In this work we show that the answer is no. We present an LCL problem $\Pi$
such that the round complexity of $\Pi$ is $\Omega(\sqrt n)$ in the usual
randomized \local model with private randomness, but if the nodes have access
to a source of shared randomness, then the complexity drops to $O(\log n)$.
  As corollaries, we also resolve several other open questions related to the
landscape of distributed computing in the context of LCL problems. In
particular, problem $\Pi$ demonstrates that distributed quantum algorithms for
LCL problems strictly benefit from a shared quantum state. Problem $\Pi$ also
gives a separation between finitely dependent distributions and non-signaling
distributions.
