  Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted
setting, the dependency of the complexity of the distributed Lov\'asz Local
Lemma (LLL) on the chosen LLL criterion exhibits a sharp threshold phenomenon:
They proved that, under the LLL criterion $p2^d < 1$, if each random variable
affects at most $3$ events, the deterministic complexity of the LLL in the
LOCAL model is $O(d^2 + \log^* n)$. In stark contrast, under the criterion
$p2^d \leq 1$, there is a randomized lower bound of $\Omega(\log \log n)$ by
Brandt et al. [STOC'16] and a deterministic lower bound of $\Omega(\log n)$ by
Chang, Kopelowitz and Pettie [FOCS'16]. Brandt, Maus and Uitto conjectured that
the same behavior holds for the unrestricted setting where each random variable
affects arbitrarily many events.
  We prove their conjecture, by providing an algorithm that solves the LLL in
time $O(d^2 + \log^* n)$ under the LLL criterion $p2^d < 1$, which is tight in
bounded-degree graphs due to an $\Omega(\log^* n)$ lower bound by Chung, Pettie
and Su [PODC'14]. By the work of Brandt, Maus and Uitto, obtaining such an
algorithm can be reduced to proving that all members in a certain family of
functions in arbitrarily high dimensions are convex on some specific domain.
Unfortunately, an analytical description of these functions is known only for
dimension at most $3$, which led to the aforementioned restriction of their
result. While obtaining those descriptions for functions of (substantially)
higher dimension seems out of the reach of current techniques, we show that
their convexity can be inferred by combinatorial means.
