  The Local Computation Algorithm (LCA) model is a popular model in the field
of sublinear-time algorithms that measures the complexity of an algorithm by
the number of probes the algorithm makes in the neighborhood of one node to
determine that node's output.
  In this paper we show that the randomized LCA complexity of the Lov\'asz
Local Lemma (LLL) on constant degree graphs is $\Theta(\log n)$. The lower
bound follows by proving an $\Omega(\log n)$ lower bound for the Sinkless
Orientation problem introduced in [Brandt et al. STOC 2016]. This answers a
question of [Rosenbaum, Suomela PODC 2020].
  Additionally, we show that every randomized LCA algorithm for a locally
checkable problem with a probe complexity of $o(\sqrt{\log{n}})$ can be turned
into a deterministic LCA algorithm with a probe complexity of $O(\log^* n)$.
This improves exponentially upon the currently best known speed-up result from
$o(\log \log n)$ to $O(\log^* n)$ implied by the result of [Chang, Pettie FOCS
2017] in the LOCAL model.
  Finally, we show that for every fixed constant $c \geq 2$, the deterministic
VOLUME complexity of $c$-coloring a bounded degree tree is $\Theta(n)$, where
the VOLUME model is a close relative of the LCA model that was recently
introduced by [Rosenbaum, Suomela PODC 2020].
