{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T15:54:14Z","timestamp":1787759654600,"version":"build-2784847793"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T00:00:00Z","timestamp":1520294400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1010789 and CCF 1422569"],"award-info":[{"award-number":["CNS 1010789 and CCF 1422569"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Adobe, Inc"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>Moser and Tardos have developed a powerful algorithmic approach (henceforth MT) to the Lov\u00e1sz Local Lemma (LLL); the basic operation done in MT and its variants is a search for \u201cbad\u201d events in a current configuration. In the initial stage of MT, the variables are set independently. We examine the distributions on these variables that arise during intermediate stages of MT. We show that these configurations have a more or less \u201crandom\u201d form, building further on the MT-distribution concept of Haeupler et al. in understanding the (intermediate and) output distribution of MT. This has a variety of algorithmic applications; the most important is that bad events can be found relatively quickly, improving on MT across the complexity spectrum. It makes some polynomial-time algorithms sublinear (e.g., for Latin transversals, which are of basic combinatorial interest), gives lower-degree polynomial runtimes in some settings, transforms certain superpolynomial-time algorithms into polynomial-time algorithms, and leads to Las Vegas algorithms for some coloring problems for which only Monte Carlo algorithms were known.<\/jats:p>\n                  <jats:p>We show that, in certain conditions when the LLL condition is violated, a variant of the MT algorithm can still produce a distribution that avoids most of the bad events. We show in some cases that this MT variant can run faster than the original MT algorithm itself and develop the first-known criterion for the case of the asymmetric LLL. This can be used to find partial Latin transversals\u2014improving on earlier bounds of Stein (1975)\u2014among other applications. We furthermore give applications in enumeration, showing that most applications (for which we aim for all or most of the bad events to be avoided) have large solution sets. We do this by showing that the MT distribution has large R\u00e9nyi entropy.<\/jats:p>","DOI":"10.1145\/3039869","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T14:12:04Z","timestamp":1488895924000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution"],"prefix":"10.1145","volume":"13","author":[{"given":"David G.","family":"Harris","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.59"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.063"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10057"},{"key":"e_1_2_1_4_1","volume-title":"Spencer","author":"Alon Noga","year":"2004","unstructured":"Noga Alon and Joel H. Spencer. 2004. The Probabilistic Method. John Wiley 8 Sons, New York, NY."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000253"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90011-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325708"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803400"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897528"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20556"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897530"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3070-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90040-4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133088"},{"key":"e_1_2_1_16_1","volume-title":"Graph Theory in Paris","author":"Grytczuk Jaros\u0142aw","unstructured":"Jaros\u0142aw Grytczuk. 2006. Nonrepetitive graph coloring. In Graph Theory in Paris. Springer, 209--218."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1155\/2007\/74639"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039762"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.09.027"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722249"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.57"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634142"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.85"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1770310.1770339"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00187-9"},{"key":"e_1_2_1_27_1","volume-title":"Szekely","author":"Lu Linyuan","year":"2009","unstructured":"Linyuan Lu and Laszlo A. Szekely. 2009. A new asymptotic enumeration technique: The Lov\u00e1sz local lemma. arXiv Preprint arXiv:0905.3983."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.015"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/110828290"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796462"},{"key":"e_1_2_1_34_1","unstructured":"Herbert J. Ryser. 1967. Neuere probleme der kombinatorik. Vortr\u00e4ge \u00fcber Kombinatorik Oberwolfach 69--91."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(82)90074-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","unstructured":"Joel Spencer. 1977. Asymptotic lower bounds for Ramsey functions. Discrete Mathematics 20 69--76. 10.1016\/0012-365X(77)90044-9","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1975.59.567"},{"key":"e_1_2_1_38_1","first-page":"1","article-title":"Uber unendliche zeichenreihen","volume":"7","author":"Thue Axel","year":"1906","unstructured":"Axel Thue. 1906. Uber 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_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2464831"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039869","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039869","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:27:45Z","timestamp":1763458065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039869"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3039869"],"URL":"https:\/\/doi.org\/10.1145\/3039869","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,6]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}