We show that any randomised Monte Carlo distributed algorithm for the Lov 'asz local lemma requires @math communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of @math , where @math is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lov 'asz local lemma with a running time of @math rounds in bounded-degree graphs, and the best lower bound before our work was @math rounds [ 2014].
@cite_19: 
@cite_5: The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents an extremely simple randomized algorithm providing a near-optimal local complexity for this problem, which incidentally, when combined with some recent techniques, also leads to a near-optimal global complexity. Classical algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability, all nodes terminate after @math rounds. In contrast, our initial focus is on the local complexity, and our main contribution is to provide a very simple algorithm guaranteeing that each particular node @math terminates after @math rounds, with probability at least @math . The guarantee holds even if the randomness outside @math -hops neighborhood of @math is determined adversarially. This degree-dependency is optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Interestingly, this local complexity smoothly transitions to a global complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider [FOCS'12, arXiv: 1202.1983v3], we get a randomized MIS algorithm with a high probability global complexity of @math , where @math denotes the maximum degree. This improves over the @math result of , and gets close to the @math lower bound of Corollaries include improved algorithms for MIS in graphs of upper-bounded arboricity, or lower-bounded girth, for Ruling Sets, for MIS in the Local Computation Algorithms (LCA) model, and a faster distributed algorithm for the Lov 'asz Local Lemma.
@cite_14: The Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Bec91], Beck demonstrated that a constructive variant can be given under certain more restrictive conditions. Simplifications of his procedure and relaxations of its restrictions were subsequently exhibited in several publications [Alo91, MR98, CS00, Mos06, Sri08, Mos08]. In [Mos09], a constructive proof was presented that works under negligible restrictions, formulated in terms of the Bounded Occurrence Satisfiability problem. In the present paper, we reformulate and improve upon these findings so as to directly apply to almost all known applications of the general Local Lemma.
As pointed out by Moser and Tardos @cite_14 , it is not necessary to find a independent set, but a large independent set suffices. Following this idea, @cite_19 gave a distributed algorithm where they instead compute so-called independent sets, where the probability that a node is not in the produced independent set @math or neighbouring a node in set @math is bounded by @math . They showed that this can be done in @math rounds, thus the dependency on @math in the total running time of the LLL algorithm is only @math . Recently, Ghaffari improved this further by showing that weakly maximal independent sets can be computed in @math rounds @cite_5 .