Deterministic algorithms for the Lovasz local lemma: Simpler, more general, and more parallel

The Lovasz local lemma (LLL) is a keystone principle in probability theory, guaranteeing the existence of configurations which avoid a collection B of bad events which are mostly independent and have low probability. A seminal algorithm of Moser and Tardos (J. ACM, 2010, 57, 11) (which we call the MT algorithm) gives nearly-automatic randomized algorithms for most constructions based on the LLL. However, deterministic algorithms have lagged behind. We address three specific shortcomings of the prior deterministic algorithms. First, our algorithm applies to the LLL criterion of Shearer (Combinatorica, 1985, 5, 241-245); this is more powerful than alternate LLL criteria and also leads to cleaner and more legible bounds. Second, we provide parallel algorithms with much greater flexibility. Third, we provide a derandomized version of the MT-distribution, that is, the distribution of the variables at the termination of the MT algorithm. We show applications to non-repetitive vertex coloring, independent transversals, strong coloring, and other problems.

Automated summary

The Lovasz local lemma guarantees the existence of configurations that avoid a collection of mostly independent bad events. The MT algorithm provides randomized algorithms for constructions based on the LLL, while deterministic algorithms have been lacking. The authors address three specific shortcomings of prior deterministic algorithms and provide applications to various problems.