Deterministic Algorithms for the Lovász Local Lemma
The Lovász local lemma (LLL) [P. Erdös and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and Finite Sets, Vol. II, A. Hajnal, R. Rado, and V. T. Sós, eds., North--Holland, Amsterdam, 1975, pp. 609--627] is a powerful result in probability theory t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/85941 https://orcid.org/0000-0003-3381-0459 |
| _version_ | 1826217398181560320 |
|---|---|
| author | Chandrasekaran, Karthekeyan Goyal, Navin Haeupler, Bernhard |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Chandrasekaran, Karthekeyan Goyal, Navin Haeupler, Bernhard |
| author_sort | Chandrasekaran, Karthekeyan |
| collection | MIT |
| description | The Lovász local lemma (LLL) [P. Erdös and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and Finite Sets, Vol. II, A. Hajnal, R. Rado, and V. T. Sós, eds., North--Holland, Amsterdam, 1975, pp. 609--627] is a powerful result in probability theory that informally states the following: the probability that none of a set of bad events happens is positive if the probability of each event is small compared to the number of events that depend on it. The LLL is often used for nonconstructive existence proofs of combinatorial structures. A prominent application is to $k$-CNF formulas, where the LLL implies that if every clause in a formula shares variables with at most $d \leq 2^k/e-1$ other clauses, then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment in this setting was given by Moser [A constructive proof of the Lovász local lemma, in STOC '09: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM, New York, 2009, pp. 343--350]. Subsequently Moser and Tardos [J. ACM, 57 (2010), pp. 11:1--11:15] gave a general algorithmic framework for the LLL and a randomized algorithm within this framework to construct the structures guaranteed by the LLL. The main problem left open by Moser and Tardos was to design an efficient deterministic algorithm for constructing structures guaranteed by the LLL. In this paper we provide such an algorithm. Our algorithm works in the general framework of Moser and Tardos with a minimal loss in parameters. For the special case of constructing satisfying assignments for $k$-CNF formulas with $m$ clauses, where each clause shares variables with at most $d \leq 2^{k/(1+\epsilon)}/e - 1$ other clauses, for any $\epsilon\in (0,1)$, we give a deterministic algorithm that finds a satisfying assignment in time $\tilde{O}(m^{2(1+1/\epsilon)})$. This improves upon the deterministic algorithms of Moser and of Moser and Tardos with running times $m^{\Omega(k^2)}$ and $m^{\Omega(d \log d)}$, respectively, which are superpolynomial for $k=\omega(1)$ and $d=\omega(1)$, and upon the previous best deterministic algorithm of Beck, which runs in polynomial time only for $d\leq 2^{k/16}/4$. Our algorithm is the first deterministic algorithm that works in the general framework of Moser and Tardos. We also give a parallel NC algorithm for the same setting, improving upon an algorithm of Alon [Random Structures Algorithms, 2 (1991), pp. 367--378]. |
| first_indexed | 2024-09-23T17:03:00Z |
| format | Article |
| id | mit-1721.1/85941 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:03:00Z |
| publishDate | 2014 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/859412022-10-03T10:01:10Z Deterministic Algorithms for the Lovász Local Lemma Chandrasekaran, Karthekeyan Goyal, Navin Haeupler, Bernhard Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Haeupler, Bernhard The Lovász local lemma (LLL) [P. Erdös and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and Finite Sets, Vol. II, A. Hajnal, R. Rado, and V. T. Sós, eds., North--Holland, Amsterdam, 1975, pp. 609--627] is a powerful result in probability theory that informally states the following: the probability that none of a set of bad events happens is positive if the probability of each event is small compared to the number of events that depend on it. The LLL is often used for nonconstructive existence proofs of combinatorial structures. A prominent application is to $k$-CNF formulas, where the LLL implies that if every clause in a formula shares variables with at most $d \leq 2^k/e-1$ other clauses, then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment in this setting was given by Moser [A constructive proof of the Lovász local lemma, in STOC '09: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM, New York, 2009, pp. 343--350]. Subsequently Moser and Tardos [J. ACM, 57 (2010), pp. 11:1--11:15] gave a general algorithmic framework for the LLL and a randomized algorithm within this framework to construct the structures guaranteed by the LLL. The main problem left open by Moser and Tardos was to design an efficient deterministic algorithm for constructing structures guaranteed by the LLL. In this paper we provide such an algorithm. Our algorithm works in the general framework of Moser and Tardos with a minimal loss in parameters. For the special case of constructing satisfying assignments for $k$-CNF formulas with $m$ clauses, where each clause shares variables with at most $d \leq 2^{k/(1+\epsilon)}/e - 1$ other clauses, for any $\epsilon\in (0,1)$, we give a deterministic algorithm that finds a satisfying assignment in time $\tilde{O}(m^{2(1+1/\epsilon)})$. This improves upon the deterministic algorithms of Moser and of Moser and Tardos with running times $m^{\Omega(k^2)}$ and $m^{\Omega(d \log d)}$, respectively, which are superpolynomial for $k=\omega(1)$ and $d=\omega(1)$, and upon the previous best deterministic algorithm of Beck, which runs in polynomial time only for $d\leq 2^{k/16}/4$. Our algorithm is the first deterministic algorithm that works in the general framework of Moser and Tardos. We also give a parallel NC algorithm for the same setting, improving upon an algorithm of Alon [Random Structures Algorithms, 2 (1991), pp. 367--378]. Massachusetts Institute of Technology (Akamai Presidential Fellowship) 2014-03-28T13:39:52Z 2014-03-28T13:39:52Z 2013-11 2013-07 Article http://purl.org/eprint/type/JournalArticle 0097-5397 1095-7111 http://hdl.handle.net/1721.1/85941 Chandrasekaran, Karthekeyan, Navin Goyal, and Bernhard Haeupler. “Deterministic Algorithms for the Lovász Local Lemma.” SIAM Journal on Computing 42, no. 6 (January 2013): 2132–2155. https://orcid.org/0000-0003-3381-0459 en_US http://dx.doi.org/10.1137/100799642 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics Society for Industrial and Applied Mathematics |
| spellingShingle | Chandrasekaran, Karthekeyan Goyal, Navin Haeupler, Bernhard Deterministic Algorithms for the Lovász Local Lemma |
| title | Deterministic Algorithms for the Lovász Local Lemma |
| title_full | Deterministic Algorithms for the Lovász Local Lemma |
| title_fullStr | Deterministic Algorithms for the Lovász Local Lemma |
| title_full_unstemmed | Deterministic Algorithms for the Lovász Local Lemma |
| title_short | Deterministic Algorithms for the Lovász Local Lemma |
| title_sort | deterministic algorithms for the lovasz local lemma |
| url | http://hdl.handle.net/1721.1/85941 https://orcid.org/0000-0003-3381-0459 |
| work_keys_str_mv | AT chandrasekarankarthekeyan deterministicalgorithmsforthelovaszlocallemma AT goyalnavin deterministicalgorithmsforthelovaszlocallemma AT haeuplerbernhard deterministicalgorithmsforthelovaszlocallemma |