Distributed Algorithms for the Lovász Local Lemma and Graph Coloring

The Lovasz Local Lemma (LLL), introduced by Erdos and Lovasz in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of n "bad" events do not happen with non-zero probability, provided that the events have limited dependence. However, the LLL itself does not suggest how to find a point avoiding all bad events. Since the work of Beck (1991)
there has been a sustained effort in finding a constructive proof (i.e. an algorithm) for the LLL or weaker versions of it. In a major breakthrough Moser and Tardos (2010) showed that a point avoiding all bad events can be found efficiently. They also proposed a distributed/parallel version of their algorithm that requires O(log^2 n) rounds of communication in a distributed network.

In many graph coloring problems, the existence of a valid coloring is established by one or more applications of the LLL. I will present distributed algorithms for the LLL that improve on both the efficiency and simplicity of the Moser-Tardos algorithm and their applications. Using our LLL algorithms, frugal coloring, defective coloring, coloring girth-4 (triangle-free) and girth-5 graphs, edge coloring, and list coloring can be obtained in logarithmic distributed rounds. Finally, we show that any distributed LLL algorithm requires \Omega(log* n) rounds.

joint work with Kai-Min Chung and Seth Pettie