×
Moser, Robin A.

A constructive proof of the Lovász local lemma. (English) Zbl 1304.68079

Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 343-350 (2009).

Cited in 2 Reviews
Cited in 44 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68W20 Randomized algorithms

Keywords:

Lovász local lemma; bounded occurrence SAT instances; derandomization; hypergraph colouring

Citations:

Zbl 0756.05080
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Donald E. Knuth. The Art of Computer Programming, Vol. I, Addison Wesley, London, 1969, p. 396 (Exercise 11). · Zbl 0191.18001
[2] Paul Erdos and Laszlo Lovasz. Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado and V.T. Sos, editors, Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday), volume II, pages 609-627. North-Holland, 1975. · Zbl 0315.05117
[3] Joszef Beck. An Algorithmic Approach to the Lovasz Local Lemma. Random Structures and Algorithms, 2(4):343-365, 1991. · Zbl 0756.05080
[4] Noga Alon. A parallel algorithmic version of the local lemma. Random Structures and Algorithms, 2(4):367-378, 1991. · Zbl 0768.05086
[5] Jan Kratochv1l and Petr Savicky and Zsolt Tuza. One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM J. Comput., Vol. 22, No. 1, pp. 203-210, 1993. 10.1137/0222015 · Zbl 0767.68057
[6] Michael Molloy and Bruce Reed. Further Algorithmic Aspects of the Local Lemma. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, pages 524-529, 1998. 10.1145/276698.276866 · Zbl 1028.68105
[7] Artur Czumaj and Christian Scheideler. Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovasz local lemma. Symposium on Discrete Algorithms, 30-39, 2000. · Zbl 0954.05020
[8] Robin A. Moser. On the Search for Solutions to Bounded Occurrence Instances of SAT. Not published. Semester Thesis, ETH Zurich. 2006.
[9] Aravind Srinivasan. Improved algorithmic versions of the Lovasz Local Lemma. Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), San Francisco, California, pp. 611-620, 2008. · Zbl 1192.68837
[10] Emo Welzl. Boolean Satisfiability – Combinatorics and Algorithms. Lecture notes, Version Fall 2008.
[11] Robin A. Moser. Derandomizing the Lovasz Local Lemma more Effectively. Eprint, arXiv:0807.2120v2, 2008.
[12] Robin A. Moser and Gabor Tardos. A constructive proof of the general Lovasz Local Lemma. Eprint, arXiv:0903.0544v2, 2009.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.