Distributed algorithms for the Lovász local lemma and graph coloring. Submitted to PODC 2014. Full version available at http://web.eecs.umich.edu/∼pettie

The Lovász Local Lemma (LLL), introduced by Erdős 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 to find 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(log2 n) rounds of communication in a distributed network. In this paper we provide two new distributed algorithm