Moser and Tardos meet Lovász

Kashyap Babu Rao Kolipaka, Mario Szegedy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

61 Scopus citations

Abstract

Beck's early work [3] gave an efficient version of the Lovász Local Lemma(LLL) with significant compromise in the parameters. Following several improvements [1,7,4,13], Moser [8], and Moser and Tardos [9] obtained asymptotically optimal results in terms of the maximal degree. For a fixed dependency graph G the exact criterion under which LLL applies is given by Shearer in [12]. For a dependency structure G, let LO(G) be the set of those probability assignments to the nodes of G for which the Lovász Local Lemma holds. We show that: Both the sequential and parallel ersions of the Moser-Tardos algorithm are efficient up to the Shearer's bound, by giving a tighter analysis. We also prove that, whenever p ∈ LO(G)/(1+∈), the expected running times of the sequential and parallel versions are at most n/∈ and O(1/∈ log n/∈), the later when ∈ < 1. Here n is the number of nodes in G. By adding a few lines to our analysis we can reprove Shearer's result (for the general LLL). Our alternative proof for the Shearer's bound not only highlights the connection between the variable and general versions of LLL, but also illustrates that variants of the Moser-Tardos algorithm can be useful in existence proofs. We obtain new formulas for phase transitions in the hardcore lattice gas model, non-trivially equivalent to the ones studied by Scott and Sokal [10]. We prove that if p ∈ LO(G)/(1+∈), the running time of the Moser-Tardos algorithm is polynomial not only in the number of events, but also in the number of variables. This extends one of the results from the more recent work of Haeupler, Saha, and Srinivasan [6]. Our new formulas immediately give a majorizing lemma that connects LLL bounds on different graphs. We show that the LLL bound for the (special case of the) variable version is sometimes larger than for the general version. This is the first known separation between the variable and the general versions of LLL.

Original languageEnglish (US)
Title of host publicationSTOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
Pages235-243
Number of pages9
DOIs
StatePublished - 2011
Event43rd ACM Symposium on Theory of Computing, STOC'11 - San Jose, CA, United States
Duration: Jun 6 2011Jun 8 2011

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other43rd ACM Symposium on Theory of Computing, STOC'11
Country/TerritoryUnited States
CitySan Jose, CA
Period6/6/116/8/11

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Lovász local lemma
  • hardcore lattice gas
  • independent set polynomial
  • matrix iterative analysis

Fingerprint

Dive into the research topics of 'Moser and Tardos meet Lovász'. Together they form a unique fingerprint.

Cite this