Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
Abstract The Lovász local lemma (LLL) is a keystone principle in probability theory, guaranteeing the existence of configurations which avoid a collection 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 …