Paper Info
Title
Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications
Abstract
Following the groundbreaking algorithm of Moser and Tardos for the Lovasz Local Lemma (LLL), there has been a plethora of results analyzing local search algorithms for various constraint satisfaction problems. The algorithms considered fall into two broad categories: resampling algorithms, analyzed via different algorithmic LLL conditions; and backtracking algorithms, analyzed via entropy compression arguments. This paper introduces a new convergence condition that seamlessly handles resampling, backtracking, and hybrid algorithms, i.e., algorithms that perform both resampling and backtracking steps. Unlike previous work on the LLL, our condition replaces the notion of a dependency or causality graph by quantifying point-to-set correlations between bad events. As a result, our condition simultaneously: (i) captures the most general algorithmic LLL condition known as a special case; (ii) significantly simplifies the analysis of entropy compression applications; (iii) relates backtracking algorithms, which are conceptually very different from resampling algorithms, to the LLL; and most importantly (iv) allows for the analysis of hybrid algorithms, which were outside the scope of previous techniques. We give several applications of our condition, including a new hybrid vertex coloring algorithm that extends the recent breakthrough result of Molloy for coloring triangle-free graphs to arbitrary graphs.
Year
DOI
Venue
2019
10.1109/FOCS.2019.00049
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
Field
DocType
Local Lemma,local search algorithms,backtracking,graph coloring,random graphs
Discrete mathematics,Combinatorics,Computer science,Lovász local lemma
Conference
ISSN
ISBN
Citations 
1523-8288
978-1-7281-4953-0
0
PageRank 
References 
Authors
0.34
22
3
Name
Order
Citations
PageRank
Dimitris Achlioptas12037174.89
Fotis Iliopoulos2135.28
Alistair Sinclair31506308.40