  Locally checkable labeling problems (LCLs) are distributed graph problems in
which a solution is globally feasible if it is locally feasible in all
constant-radius neighborhoods. Vertex colorings, maximal independent sets, and
maximal matchings are examples of LCLs.
  On the one hand, it is known that some LCLs benefit exponentially from
randomness---for example, any deterministic distributed algorithm that finds a
sinkless orientation requires $\Theta(\log n)$ rounds in the LOCAL model, while
the randomized complexity of the problem is $\Theta(\log \log n)$ rounds. On
the other hand, there are also many LCLs in which randomness is useless.
  Previously, it was not known if there are any LCLs that benefit from
randomness, but only subexponentially. We show that such problems exist: for
example, there is an LCL with deterministic complexity $\Theta(\log^2 n)$
rounds and randomized complexity $\Theta(\log n \log \log n)$ rounds.
