For the distributed LLL with each variable affecting at most three events, the paper gives an O(d^2 + log* n) deterministic algorithm under the criterion p < 2^{-d}, and shows the threshold p = 2^{-d} is sharp.
A Parallel Algorithmic Version of the Local Lemma
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A Sharp Threshold Phenomenon for the Distributed Complexity of the Lov\'asz Local Lemma
For the distributed LLL with each variable affecting at most three events, the paper gives an O(d^2 + log* n) deterministic algorithm under the criterion p < 2^{-d}, and shows the threshold p = 2^{-d} is sharp.