New bounds for the Moser‐Tardos distribution. Issue 1 (2nd March 2020)

• Record Type: Journal Article
• Authors: Harris, David G.
• Is Part Of: Random structures & algorithms. Volume 57:Issue 1(2020)
• Page Start: 97
• Page End: 131
• Publication Date: 2020-03-02
• Subjects: Lovász Local Lemma -- Moser‐Tardos algorithm -- Boolean satisfiability -- Independent transversals -- Latin transversals; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20914
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : The Lovász local lemma (LLL) is a probabilistic tool to generate combinatorial structures with good "local" properties. The "LLL‐distribution" further shows that these structures have good global properties in expectation. The seminal algorithm of Moser and Tardos turned the simplest, variable‐based form of the LLL into an efficient algorithm; this has since been extended to other probability spaces including random permutations. One can similarly define an "MT‐distribution" for these algorithms, that is, the distribution of the configuration they produce. We show new bounds on the MT‐distribution in the variable and permutation settings which are significantly stronger than those known to hold for the LLL‐distribution. As some example illustrations, we show a nearly tight bound on the minimum implicate size of a CNF Boolean formula, and we obtain improved bounds on weighted Latin transversals and partial Latin transversals.