  The Lov\'{a}sz Local Lemma (LLL) says that, given a set of bad events that
depend on the values of some random variables and where each event happens with
probability at most $p$ and depends on at most $d$ other events, there is an
assignment of the variables that avoids all bad events if the LLL criterion
$ep(d+1)<1$ is satisfied.
  In this paper, we study the dependency of the distributed complexity of the
LLL problem on the chosen LLL criterion. We show that for the fundamental case
of each random variable of the considered LLL instance being associated with an
edge of the input graph, that is, each random variable influences at most two
events, a sharp threshold phenomenon occurs at $p = 2^{-d}$: we provide a
simple deterministic (!) algorithm that matches a known $\Omega(\log^* n)$
lower bound in bounded degree graphs, if $p < 2^{-d}$, whereas for $p \geq
2^{-d}$, a known $\Omega(\log \log n)$ randomized and a known $\Omega(\log n)$
deterministic lower bounds hold.
  In many applications variables affect more than two events; our main
contribution is to extend our algorithm to the case where random variables
influence at most three different bad events. We show that, surprisingly, the
sharp threshold occurs at the exact same spot, providing evidence for our
conjecture that this phenomenon always occurs at $p = 2^{-d}$, independent of
the number $r$ of events that are affected by a variable. Almost all steps of
the proof framework we provide for the case $r=3$ extend directly to the case
of arbitrary $r$; consequently, our approach serves as a step towards
characterizing the complexity of the LLL under different exponential criteria.
