Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma

Abstract

Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lovász Local Lemma (LLL) on the chosen LLL criterion exhibits a sharp threshold phenomenon: They proved that, under the LLL criterion p2d < 1, if each random variable affects at most 3 events, the deterministic complexity of the LLL in the LOCAL model is O(d2 + log* n). In stark contrast, under the criterion p2d ≤ 1, there is a randomized lower bound of Ω(log log n) by Brandt et al. [STOC'16] and a deterministic lower bound of Ω(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.

Locations

• arXiv (Cornell University) - View - PDF