Hsin-Hao Su: Distributed Algorithms for the Lovasz Local Lemma and Graph Coloring

Abstract: The Lovász Local Lemma (LLL), introduced by Erdos and Lovász 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.

In many graph coloring problems, the existence of a valid coloring is established by one or more applications of the LLL. I will talk about how to convert the existential proofs into efficient coloring algorithms in the distributed network. Then, I will present our distributed algorithms for LLL that improve on both the efficiency and simplicity of the Moser-Tardos algorithm. Using our LLL algorithms, we show problems such as edge coloring, triangle-free graphs coloring, list coloring, frugal coloring, and defective coloring can be solved in logarithmic distributed rounds.