{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T10:58:05Z","timestamp":1763809085024,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0728839CCF-0937865CNS-0626636CNS-1010789"],"award-info":[{"award-number":["CCF-0728839CCF-0937865CNS-0626636CNS-1010789"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CCF-0728839CCF-0937865CNS-0626636CNS-1010789","CNS-0426683"],"award-info":[{"award-number":["CCF-0728839CCF-0937865CNS-0626636CNS-1010789","CNS-0426683"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>\n            The Lov\u00e1sz Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of \u201cbad\u201d events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser and Tardos [2010] for the full asymmetric LLL. We show that the output distribution of the Moser-Tardos algorithm well-approximates the\n            <jats:italic>conditional LLL-distribution<\/jats:italic>\n            , the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and nonconstructive results.\n          <\/jats:p>\n          <jats:p>\n            We also show that when a LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized \u201ccore\u201d subset of bad events leads to a desired outcome with high probability. This is shown via a simple union bound over the probabilities of non-core events in the conditional LLL-distribution, and automatically leads to simple and efficient Monte-Carlo (and in most cases\n            <jats:italic>RNC<\/jats:italic>\n            ) algorithms. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making a LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, nonrepetitive graph colorings, and Ramsey-type graphs. In all these applications, the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known.\n          <\/jats:p>\n          <jats:p>\n            As a second type of application we show that the properties of the conditional LLL-distribution can be used in cases beyond the critical dependency threshold of the LLL: avoiding all bad events is impossible in these cases. As the first (even nonconstructive) result of this kind, we show that by sampling a selected smaller core from the LLL-distribution, we can avoid a fraction of bad events that is higher than the expectation. MAX\n            <jats:italic>k<\/jats:italic>\n            -SAT is an illustrative example of this.\n          <\/jats:p>","DOI":"10.1145\/2049697.2049702","type":"journal-article","created":{"date-parts":[[2011,12,13]],"date-time":"2011-12-13T15:45:47Z","timestamp":1323791147000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["New Constructive Aspects of the Lov\u00e1sz Local Lemma"],"prefix":"10.1145","volume":"58","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology"}]},{"given":"Barna","family":"Saha","sequence":"additional","affiliation":[{"name":"AT&amp;T Shannon Research Laboratory"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland College Park"}]}],"member":"320","published-online":{"date-parts":[[2011,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"12","DOI":"10.37236\/1192","article-title":"Explicit Ramsey graphs and orthonormal labelings","volume":"1","author":"Alon N.","year":"1994","unstructured":"Alon , N. 1994 . Explicit Ramsey graphs and orthonormal labelings . Electron. J. Combin. 1 , 12 -- 18 . Alon, N. 1994. Explicit Ramsey graphs and orthonormal labelings. Electron. J. Combin. 1, 12--8.","journal-title":"Electron. J. Combin."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03352998"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.063"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02809902"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Alon N. and Spencer J. H. 2008. The Probabilistic Method 3rd Ed. Wiley. Alon N. and Spencer J. H. 2008. The Probabilistic Method 3rd Ed. Wiley.","DOI":"10.1002\/9780470277331"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v37:3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10057"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020303"},{"volume-title":"Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Alon N.","key":"e_1_2_1_11_1","unstructured":"Alon , N. , Gutin , G. , Kim , E. J. , Szeider , S. , and Yeo , A . 2010. Solving MAX-r-SAT above a tight lower bound . In Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . ACM. Alon, N., Gutin, G., Kim, E. J., Szeider, S., and Yeo, A. 2010. Solving MAX-r-SAT above a tight lower bound. In Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). ACM."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.33"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250808"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536488"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120680.1120683"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.06.017"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748028"},{"volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Chandrasekaran K.","key":"e_1_2_1_21_1","unstructured":"Chandrasekaran , K. , Goyal , N. , and Haeupler , B . 2010. Deterministic algorithms for the Lov\u00e1sz Local Lemma . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . 992--1004. Chandrasekaran, K., Goyal, N., and Haeupler, B. 2010. Deterministic algorithms for the Lov\u00e1sz Local Lemma. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 992--1004."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.01.004"},{"volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Czumaj A.","key":"e_1_2_1_23_1","unstructured":"Czumaj , A. and Scheideler , C . 2000. Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lov\u00e1sz local lemma . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900) . 30--39. Czumaj, A. and Scheideler, C. 2000. Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lov\u00e1sz local lemma. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900). 30--39."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"e_1_2_1_25_1","volume-title":"Colloq. Math. Soc., J. Bolyai Series","volume":"11","author":"Erd\u0151s P.","unstructured":"Erd\u0151s , P. and Lov\u00e1sz , L . 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets , Colloq. Math. Soc., J. Bolyai Series , vol. 11 , North-Holland, 609--627. Erd\u0151s, P. and Lov\u00e1sz, L. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, Colloq. Math. Soc., J. Bolyai Series, vol. 11, North-Holland, 609--627."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Feige U.","year":"2008","unstructured":"Feige , U. 2008 a. On allocations that maximize fairness . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . 287--293. Feige, U. 2008a. On allocations that maximize fairness. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 287--293."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Annual Conference on Foundation of Structure Technology and Theoritical Computer Science (FSTTCS). LIPIcs Series","volume":"2","author":"Feige U.","year":"2008","unstructured":"Feige , U. 2008 b. On estimation algorithms vs approximation algorithms . In Proceedings of the Annual Conference on Foundation of Structure Technology and Theoritical Computer Science (FSTTCS). LIPIcs Series , vol. 2 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 357--363. Feige, U. 2008b. On estimation algorithms vs approximation algorithms. In Proceedings of the Annual Conference on Foundation of Structure Technology and Theoritical Computer Science (FSTTCS). LIPIcs Series, vol. 2. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 357--363."},{"key":"e_1_2_1_28_1","unstructured":"Graham R. L. Rothschild B. L. and Spencer J. H. 1990. Ramsey Theory 2nd Ed. Wiley. Graham R. L. Rothschild B. L. and Spencer J. H. 1990. Ramsey Theory 2nd Ed . Wiley."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02764716"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.039"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01793010"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070204"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.043"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.015"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Molloy M. and Reed B. 2001. Graph Colouring and the Probabilistic Method. Springer-Verlag. Molloy M. and Reed B. 2001. Graph Colouring and the Probabilistic Method . Springer-Verlag.","DOI":"10.1007\/978-3-642-04016-0"},{"key":"e_1_2_1_40_1","unstructured":"Moser R. A. 2008. Derandomizing the Lov\u00e1sz Local Lemma more effectively. CoRR abs\/0807.2120. Moser R. A. 2008. Derandomizing the Lov\u00e1sz Local Lemma more effectively. CoRR abs\/0807.2120 ."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536462"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.03.006"},{"volume-title":"Proceedings of the 1st Annual Symposium on Innovations in Computer Science (ICS\u201910)","author":"Saha B.","key":"e_1_2_1_44_1","unstructured":"Saha , B. and Srinivasan , A . 2010. A new approximation technique for resource-allocation problems . In Proceedings of the 1st Annual Symposium on Innovations in Computer Science (ICS\u201910) . 342--357. Saha, B. and Srinivasan, A. 2010. A new approximation technique for resource-allocation problems. In Proceedings of the 1st Annual Symposium on Innovations in Computer Science (ICS\u201910). 342--357."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/582475.582484"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Srinivasan A.","year":"2008","unstructured":"Srinivasan , A. 2008 . Improved algorithmic versions of the Lov\u00e1sz Local Lemma . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . 611--620. Srinivasan, A. 2008. Improved algorithmic versions of the Lov\u00e1sz Local Lemma. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 611--620."},{"key":"e_1_2_1_47_1","first-page":"1","article-title":"\u00dcber unendliche Zeichenreihen","volume":"7","author":"Thue A.","year":"1906","unstructured":"Thue , A. 1906 . \u00dcber unendliche Zeichenreihen . Norske Vid Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 , 1 -- 22 . Thue, A. 1906. \u00dcber unendliche Zeichenreihen. Norske Vid Selsk. Skr. I. Mat. Nat. Kl. Christiana 7, 1--22.","journal-title":"Norske Vid Selsk. Skr. I. Mat. Nat. Kl. Christiana"},{"key":"e_1_2_1_48_1","first-page":"25","article-title":"On an estimate of the chromatic class of a p graph (in russian)","volume":"3","author":"Vizing V. G.","year":"1964","unstructured":"Vizing , V. G. 1964 . On an estimate of the chromatic class of a p graph (in russian) . Metody Diskret. Analiz. 3 , 25 -- 30 . Vizing, V. G. 1964. On an estimate of the chromatic class of a p graph (in russian). Metody Diskret. Analiz. 3, 25--30.","journal-title":"Metody Diskret. Analiz."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049697.2049702","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2049697.2049702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:41Z","timestamp":1750278401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049697.2049702"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2049697.2049702"],"URL":"https:\/\/doi.org\/10.1145\/2049697.2049702","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}