## 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 language | English (US) |
---|---|

Title of host publication | STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing |

Pages | 235-243 |

Number of pages | 9 |

DOIs | |

State | Published - 2011 |

Event | 43rd ACM Symposium on Theory of Computing, STOC'11 - San Jose, CA, United States Duration: Jun 6 2011 → Jun 8 2011 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 43rd ACM Symposium on Theory of Computing, STOC'11 |
---|---|

Country/Territory | United States |

City | San Jose, CA |

Period | 6/6/11 → 6/8/11 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

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