research-article

A constructive proof of the general lovász local lemma

Authors:

Robin A. Moser,

Gábor TardosAuthors Info & Claims

Journal of the ACM (JACM), Volume 57, Issue 2

Article No.: 11, Pages 1 - 15

https://doi.org/10.1145/1667053.1667060

Published: 08 February 2010 Publication History

Get Access

Abstract

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 constructive variant can be given under certain more restrictive conditions, starting a whole line of research aimed at improving his algorithm's performance and relaxing its restrictions. In the present article, we improve upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic.

References

[1]

Alon, N. 1991. A parallel algorithmic version of the local lemma. Rand. Struct. Algor. 2, 4, 367--378.

Digital Library

Google Scholar

[2]

Beck, J. 1991. An algorithmic approach to the Lovász local lemma. Rand. Struct. Algor. 2, 4, 343--365.

Digital Library

Google Scholar

[3]

Berman, P., Karpinski, M., and Scott, A. D. 2003. Approximation hardness and satisfiability of bounded occurrence instances of SAT. Electron. Colloq. Computat. Complex. 10, 022.

Google Scholar

[4]

Chandrasekaran, K., Goyal, N., and Haeupler, B. To appear in 2010. Deterministic algorithms for the Lovász local lemma. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York.

Digital Library

Google Scholar

[5]

Czumaj, A., and Scheideler, C. 2000. Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 30--39.

Digital Library

Google Scholar

[6]

Erdős, P., and Lovász, L. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado and V.T. Sós, Eds. Infinite and Finite Sets, North-Holland, II, 609--627.

Google Scholar

[7]

Erdős, P., and Spencer, J. 1991. Lopsided Lovász local lemma and Latin transversals. Discr. Appl. Math. 30, 2-3, 151--154.

Digital Library

Google Scholar

[8]

Gasarch, W. 2009. Constructive lower bounds on several Ramsey numbers via the constructive Lovász local lemma. Manuscript. www.cs.umd.edu/~gasarch/v.pdf.

Google Scholar

[9]

Molloy, M., and Reed, B. 1998. Further algorithmic aspects of the local lemma. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC). ACM, New York, 524--529.

Digital Library

Google Scholar

[10]

Moser, R. A. 2008. Derandomizing the Lovász local lemma more effectively. Eprint arXiv:0807.2120v2.

Google Scholar

[11]

Moser, R. A. 2009. A constructive proof of the Lovász local lemma. In Proceedings of the 41st Annual ACM Symposium on the Theory of Computing (STOC). ACM, New York.

Digital Library

Google Scholar

[12]

Pach, J., and Tardos, G. 2010. Conflict-free colorings of graphs and hypergraphs. Combinat. Probab. Comput.

Digital Library

Google Scholar

[13]

Schweitzer, P. 2009. Using the incompressibility method to obtain local lemma type results for Ramsey-type problems. Inform. Process. Lett. 109, 4, 229--232.

Digital Library

Google Scholar

[14]

Srinivasan, A. 2008. Improved algorithmic versions of the Lovász local lemma. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 611--620.

Digital Library

Google Scholar

Cited By

View all

Dalai MDella Fiore SRescigno AVaccaro U(2025)An efficient algorithm for group testing with runlength constraintsDiscrete Applied Mathematics10.1016/j.dam.2024.09.001360(181-187)Online publication date: Jan-2025
https://doi.org/10.1016/j.dam.2024.09.001
Jerrum M(2024)Fundamentals of partial rejection samplingProbability Surveys10.1214/24-PS2921:noneOnline publication date: 1-Jan-2024
https://doi.org/10.1214/24-PS29
Jing YMohar B(2024)Efficient polynomial-time approximation scheme for the genus of dense graphsJournal of the ACM10.1145/369082171:6(1-33)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1145/3690821
Show More Cited By

Index Terms

A constructive proof of the general lovász local lemma
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
  2. Probability and statistics

Recommendations

A constructive proof of the Lovász local lemma
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

The Lovasz Local Lemma [2] is a powerful tool to prove the existence of combinatorial objects meeting a prescribed collection of criteria. The technique can directly be applied to the satisfiability problem, yielding that a k-CNF formula in which each ...
Directed Lovász local lemma and Shearer’s lemma
Abstract
Moser and Tardos (J. ACM (JACM) 57(2), 11 2010) gave an algorithmic proof of the lopsided Lovász local lemma (LLL) in the variable framework, where each of the undesirable events is assumed to depend on a subset of a collection of independent ...
A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability

The Lovasz Local Lemma provides a syntactic property that a Boolean formula is satisifiable. Moser and Tardos came up with a constructive proof of the lemma, i.e. the proof gives a method to actually construct a satisfying assignment. In this paper, we ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 57, Issue 2

January 2010

248 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1667053

Issue’s Table of Contents

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 ACM 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: 08 February 2010

Accepted: 01 August 2009

Received: 01 May 2009

Published in JACM Volume 57, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

288
Total Citations
View Citations
3,082
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)15

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dalai MDella Fiore SRescigno AVaccaro U(2025)An efficient algorithm for group testing with runlength constraintsDiscrete Applied Mathematics10.1016/j.dam.2024.09.001360(181-187)Online publication date: Jan-2025
https://doi.org/10.1016/j.dam.2024.09.001
Jerrum M(2024)Fundamentals of partial rejection samplingProbability Surveys10.1214/24-PS2921:noneOnline publication date: 1-Jan-2024
https://doi.org/10.1214/24-PS29
Jing YMohar B(2024)Efficient polynomial-time approximation scheme for the genus of dense graphsJournal of the ACM10.1145/369082171:6(1-33)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1145/3690821
Filtser A(2024)Scattering and Sparse Partitions, and Their ApplicationsACM Transactions on Algorithms10.1145/367256220:4(1-42)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3672562
Chen ZGalanis AGoldberg LGuo HHerrera-Poyatos AMani NMoitra A(2024)Fast Sampling of Satisfying Assignments from Random $\boldsymbol{k}$-SAT with Applications to ConnectivitySIAM Journal on Discrete Mathematics10.1137/23M159572238:4(2750-2811)Online publication date: 30-Oct-2024
https://doi.org/10.1137/23M1595722
Anastos MCooley OKang MKwan M(2024)Partitioning problems via random processesJournal of the London Mathematical Society10.1112/jlms.70010110:6Online publication date: 12-Nov-2024
https://doi.org/10.1112/jlms.70010
Krishnan PMathew RKalyanasundaram S(2024)Pliable Index Coding via Conflict-Free Colorings of HypergraphsIEEE Transactions on Information Theory10.1109/TIT.2024.335541670:6(3903-3921)Online publication date: 18-Jan-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3355416
Rescigno AVaccaro U(2024)Improved Algorithms and Bounds for List Union-Free FamiliesIEEE Transactions on Information Theory10.1109/TIT.2023.331643570:4(2456-2463)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3316435
Jiang LGu YFan JMiao Y(2024)Existence and Algorithmic Construction of $q$-ary Secure Codes with List Decoding2024 IEEE Information Theory Workshop (ITW)10.1109/ITW61385.2024.10807036(585-590)Online publication date: 24-Nov-2024
https://doi.org/10.1109/ITW61385.2024.10807036
Wang CYin Y(2024)A Sampling Lovász Local Lemma for Large Domain Sizes2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00019(129-150)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00019
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

A constructive proof of the Lovász local lemma

Directed Lovász local lemma and Shearer’s lemma

A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability

Comments

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

A constructive proof of the Lovász local lemma

Directed Lovász local lemma and Shearer’s lemma

A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations