License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.44
URN: urn:nbn:de:0030-drops-94487
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9448/
Go to the corresponding LIPIcs Volume Portal

Iliopoulos, Fotis

Commutative Algorithms Approximate the LLL-distribution

pdf-format:
LIPIcs-APPROX-RANDOM-2018-44.pdf (0.5 MB)

Abstract

Following the groundbreaking Moser-Tardos algorithm for the Lovász Local Lemma (LLL), a series of works have exploited a key ingredient of the original analysis, the witness tree lemma, in order to: derive deterministic, parallel and distributed algorithms for the LLL, to estimate the entropy of the output distribution, to partially avoid bad events, to deal with super-polynomially many bad events, and even to devise new algorithmic frameworks. Meanwhile, a parallel line of work has established tools for analyzing stochastic local search algorithms motivated by the LLL that do not fall within the Moser-Tardos framework. Unfortunately, the aforementioned results do not transfer to these more general settings. Mainly, this is because the witness tree lemma, provably, does not longer hold. Here we prove that for commutative algorithms, a class recently introduced by Kolmogorov and which captures the vast majority of LLL applications, the witness tree lemma does hold. Armed with this fact, we extend the main result of Haeupler, Saha, and Srinivasan to commutative algorithms, establishing that the output of such algorithms well-approximates the LLL-distribution, i.e., the distribution obtained by conditioning on all bad events being avoided, and give several new applications. For example, we show that the recent algorithm of Molloy for list coloring number of sparse, triangle-free graphs can output exponential many list colorings of the input graph.

BibTeX - Entry

@InProceedings{iliopoulos:LIPIcs:2018:9448,
  author =	{Fotis Iliopoulos},
  title =	{{Commutative Algorithms Approximate the LLL-distribution}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{44:1--44:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9448},
  URN =		{urn:nbn:de:0030-drops-94487},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.44},
  annote =	{Keywords: Lovasz Local Lemma, Local Search, Commutativity, LLL-distribution, Coloring Triangle-free Graphs}
}

Keywords: Lovasz Local Lemma, Local Search, Commutativity, LLL-distribution, Coloring Triangle-free Graphs
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI