Paper Info
Title
The Algorithmic LLL and the Witness Tree Lemma.
Abstract
We consider the recent works of cite{AIJACM,HV,Harmonic} that provide tools for analyzing focused stochastic local search algorithms that arise from algorithmizations of the Lovasz Local Lemma cite{LLL} (LLL) in general probability spaces. These are algorithms which search a state space probabilistically by repeatedly selecting a flaw that is currently present and moving to a random nearby state in an effort to address it and, eventually, reach a flawless state. While the original Moser-Tardos cite{MT} (MT) algorithm is amenable to the analysis of these abstract frameworks, many follow-up results cite{Haeupler_jacm,EnuHarris,szege_meet,determ,distributed,ParallelHarris} that further enhance, or exploit, our understanding of the MT process are not transferable to these general settings. Mainly, this is because a key ingredient of the original analysis of Moser and Tardos, the emph{witness tree lemma}, does not longer hold. In this work, we show that we can recover the witness tree lemma in the setting. The latter was recently introduced by Kolmogorov cite{Kolmofocs} and captures the vast majority of the LLL applications. Armed with it, we focus on studying properties of commutative algorithms and give several applications. Among other things, we are able to generalize and extend to the commutative setting the main result of cite{Haeupler_jacm} which states that the output of the MT algorithm well-approximates the conditional LLL-distribution, i.e., the distribution obtained by conditioning on all bad events being avoided.
Year
Venue
Field
2017
arXiv: Discrete Mathematics
Discrete mathematics,Combinatorics,Commutative property,Computer science,Witness,Lovász local lemma,Local search (optimization),State space,Lemma (mathematics)
DocType
Volume
Citations 
Journal
abs/1704.02796
0
PageRank 
References 
Authors
0.34
11
1
Name
Order
Citations
PageRank
Fotis Iliopoulos1135.28