research-article

Random Walks That Find Perfect Objects and the Lovász Local Lemma

Authors:

Dimitris Achlioptas,

Fotis IliopoulosAuthors Info & Claims

Journal of the ACM (JACM), Volume 63, Issue 3

Article No.: 22, Pages 1 - 29

https://doi.org/10.1145/2818352

Published: 21 July 2016 Publication History

Abstract

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser’s entropic method proof of the Lovász Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser’s argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.

References

[1]

Dimitris Achlioptas and Fotis Iliopoulos. 2014. Random walks that find perfect objects and the Lovász local lemma. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, October 18--21, 2014. IEEE Computer Society, 494--503. FOCS.2014.59

Digital Library

[2]

Louigi Addario-Berry, Robert E. L. Aldred, Ketan Dalal, and Bruce A. Reed. 2005. Vertex colouring edge partitions. Journal of Combinatorial Theory, Series B 94, 2, 237--244. j.jctb.2005.01.001

Digital Library

[3]

Noga Alon. 1991. A parallel algorithmic version of the local lemma. Random Structures & Algorithms 2, 4, 367--378.

Digital Library

[4]

József Beck. 1991. An algorithmic approach to the Lovász local lemma. I. Random Structures & Algorithms 2, 4 (1991), 343--365.

Digital Library

[5]

Rodrigo Bissacot, Roberto Fernández, Aldo Procacci, and Benedetto Scoppola. 2011. An improvement of the Lovász local lemma via cluster expansion. Combinatorics, Probability & Computing 20, 5, 709--719.

Digital Library

[6]

Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. 2013. Deterministic algorithms for the Lovász local lemma. SIAM Journal on Computing 42, 6, 2132--2155.

[7]

Artur Czumaj and Christian Scheideler. 2000. Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma. Random Structures & Algorithms 17, 3--4, 213--237.

Digital Library

[8]

Persi Diaconis. 1996. The cutoff phenomenon in finite Markov chains. Proceedings of the National Academy of Sciences 93, 4, 1659--1664.

[9]

Andrzej Dudek and Michael Ferrara. 2015. Extensions of results on rainbow Hamilton cycles in uniform hypergraphs. Graphs and Combinatorics 31, 3, 577--583.

Digital Library

[10]

Andrzej Dudek, Alan M. Frieze, and Andrzej Rucinski. 2012. Rainbow Hamilton cycles in uniform hypergraphs. Electronic Journal of Combinatorics 19, 1, P46.

[11]

Paul Erdős and László Lovász. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erdős on his 60th Birthday), Vol. II. North-Holland, Amsterdam, 609--627. Colloq. Math. Soc. János Bolyai, Vol. 10.

[12]

Paul Erdös and Joel Spencer. 1991. Lopsided Lovász local lemma and latin transversals. Discrete Applied Mathematics 30, 2--3, 151--154.

Digital Library

[13]

Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. 2011. New constructive aspects of the Lovász local lemma. Journal of the ACM 58, 6, 28.

Digital Library

[14]

David G. Harris and Aravind Srinivasan. 2013. The Moser-Tardos framework with partial resampling. In 54th Annual IEEE Symposium on Foundations of Computer Science, (FOCS’13), Berkeley, CA. IEEE Computer Society, 469--478.

Digital Library

[15]

David G. Harris and Aravind Srinivasan. 2014. A constructive algorithm for the Lovász local lemma on permutations. In SODA. SIAM, 907--925.

Digital Library

[16]

Nicholas J. A. Harvey and Jan Vondrák. 2015. An algorithmic proof of the Lovász local lemma via resampling oracles. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15), Berkeley, CA. Venkatesan Guruswami (Ed.). IEEE Computer Society, 1327--1346. FOCS.2015.85

Digital Library

[17]

Rafał Kalinowski, Monika Pilśniak, Jakub Przybyło, and Mariusz Woźniak. 2013. Can colour-blind distinguish colour palettes? The Electronic Journal of Combinatorics 20, 3, P23.

[18]

Kashyap Kolipaka, Mario Szegedy, and Yixin Xu. 2012. A sharper local lemma with improved applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Anupam Gupta, Klaus Jansen, José Rolim, and Rocco Servedio (Eds.). Lecture Notes in Computer Science, Vol. 7408. Springer, Berlin, 603--614.

[19]

Kashyap Babu Rao Kolipaka and Mario Szegedy. 2011. Moser and Tardos meet Lovász. In STOC. ACM, 235--244.

Digital Library

[20]

Linyuan Lu, Austin Mohr, and László Székely. 2013. Quest for negative dependency graphs. In Recent Advances in Harmonic Analysis and Applications. Springer, 243--258.

[21]

Austin Mohr. 2013. Applications of the Lopsided Lovász Local Lemma Regarding Hypergraphs. Ph.D. Dissertation. University of South Carolina, Columbia, SC.

[22]

Michael Molloy and Bruce Reed. 1999. Further algorithmic aspects of the local lemma. In STOC’98. ACM, New York, NY, 524--529.

Digital Library

[23]

Robin A. Moser. 2009. A constructive proof of the Lovász local lemma. In Proceedings of the 2009 ACM International Symposium on Theory of Computing (STOC’09). ACM, New York, NY, 343--350.

Digital Library

[24]

Robin A. Moser and Gábor Tardos. 2010. A constructive proof of the general Lovász local lemma. Journal of the ACM 57, 2, Article 11, 15.

Digital Library

[25]

Christos H. Papadimitriou. 1991. On selecting a satisfying truth assignment. In FOCS. IEEE Computer Society, 163--169.

Digital Library

[26]

Wesley Pegden. 2011. Highly nonrepetitive sequences: Winning strategies from the local lemma. Random Structures & Algorithms 38, 1--2, 140--161.

Digital Library

[27]

Wesley Pegden. 2014. An extension of the Moser-Tardos algorithmic local lemma. SIAM Journal on Discrete Mathematics 28, 2, 911--917.

[28]

James B. Shearer. 1985. On a problem of Spencer. Combinatorica 5, 3, 241--245. 10.1007/BF02579368

Digital Library

[29]

Joel Spencer. 1977. Asymptotic lower bounds for Ramsey functions. Discrete Mathematics 20, 0, 69--76.

[30]

Aravind Srinivasan. 2008. Improved algorithmic versions of the Lovász local lemma. In SODA, Shang-Hua Teng (Ed.). SIAM, 611--620.

Digital Library

[31]

Mario Szegedy. 2013. The Lovász local lemma—a survey. In CSR, Lecture Notes in Computer Science, Andrei A. Bulatov and Arseny M. Shur (Eds.), Vol. 7913. Springer, 1--11.

Cited By

Iliopoulos FSinclair A(2022)Efficiently list‐edge coloring multigraphs asymptotically optimallyRandom Structures & Algorithms10.1002/rsa.2107461:4(724-753)Online publication date: 6-Feb-2022
https://doi.org/10.1002/rsa.21074
Feng WHe KYin YKhuller SVassilevska Williams V(2021)Sampling constraint satisfaction solutions in the local lemma regimeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451101(1565-1578)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451101
Harris D(2020)Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovász Local LemmaACM Transactions on Algorithms10.1145/339203517:1(1-32)Online publication date: 31-Dec-2020
https://dl.acm.org/doi/10.1145/3392035
Show More Cited By

Index Terms

Random Walks That Find Perfect Objects and the Lovász Local Lemma
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Random walks and Markov chains
  2. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Moser and tardos meet Lovász
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

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 ...
A constructive proof of the general lovász local lemma

The Lovász Local Lemma discovered by Erdős and Lovász in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, József Beck was the first to demonstrate that a ...
Random Walks That Find Perfect Objects and the Lovasz Local Lemma
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lovasz Local Lemma (LLL) for satisfiability ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 63, Issue 3

September 2016

303 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2957788

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2016

Accepted: 01 December 2015

Revised: 01 December 2015

Received: 01 April 2015

Published in JACM Volume 63, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

European Research Council
Alfred P. Sloan Foundation
NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
373
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Iliopoulos FSinclair A(2022)Efficiently list‐edge coloring multigraphs asymptotically optimallyRandom Structures & Algorithms10.1002/rsa.2107461:4(724-753)Online publication date: 6-Feb-2022
https://doi.org/10.1002/rsa.21074
Feng WHe KYin YKhuller SVassilevska Williams V(2021)Sampling constraint satisfaction solutions in the local lemma regimeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451101(1565-1578)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451101
Harris D(2020)Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovász Local LemmaACM Transactions on Algorithms10.1145/339203517:1(1-32)Online publication date: 31-Dec-2020
https://dl.acm.org/doi/10.1145/3392035
Achlioptas DGouleakis TIliopoulos FScheideler CSpear M(2020)Simple Local Computation Algorithms for the General Lovász Local LemmaProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400250(1-10)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400250
Harvey NVondrák J(2020)An Algorithmic Proof of the Lovász Local Lemma via Resampling OraclesSIAM Journal on Computing10.1137/18M116717649:2(394-428)Online publication date: 7-Apr-2020
https://doi.org/10.1137/18M1167176
Graf AHaxell P(2020)Finding independent transversals efficientlyCombinatorics, Probability and Computing10.1017/S0963548320000127(1-27)Online publication date: 14-May-2020
https://doi.org/10.1017/S0963548320000127
Kirousis LLivieratos JPsaromiligkos K(2020)Directed Lovász local lemma and Shearer’s lemmaAnnals of Mathematics and Artificial Intelligence10.1007/s10472-019-09671-588:1-3(133-155)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1007/s10472-019-09671-5
Harris D(2020)New bounds for the Moser‐Tardos distributionRandom Structures & Algorithms10.1002/rsa.2091457:1(97-131)Online publication date: 2-Mar-2020
https://doi.org/10.1002/rsa.20914
Harris DChan T(2019)Oblivious resampling oracles and parallel algorithms for the lopsided lovász local lemmaProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310487(841-860)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310487
Jr. GTristan J(2019)Using Butterfly-patterned Partial Sums to Draw from Discrete DistributionsACM Transactions on Parallel Computing10.1145/33656626:4(1-30)Online publication date: 19-Nov-2019
https://dl.acm.org/doi/10.1145/3365662
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents