{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T05:40:28Z","timestamp":1769233228815,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,7,21]],"date-time":"2016-07-21T00:00:00Z","timestamp":1469059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["Starting Grant 210743"],"award-info":[{"award-number":["Starting Grant 210743"]}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"crossref","award":["Research Fellowship"],"award-info":[{"award-number":["Research Fellowship"]}],"id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF-1514128, CCF-1514434"],"award-info":[{"award-number":["CCF-1514128, CCF-1514434"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser\u2019s entropic method proof of the Lov\u00e1sz Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser\u2019s argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.<\/jats:p>","DOI":"10.1145\/2818352","type":"journal-article","created":{"date-parts":[[2016,7,21]],"date-time":"2016-07-21T15:13:24Z","timestamp":1469114004000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Random Walks That Find Perfect Objects and the Lov\u00e1sz Local Lemma"],"prefix":"10.1145","volume":"63","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[{"name":"University of California Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fotis","family":"Iliopoulos","sequence":"additional","affiliation":[{"name":"University of California Berkeley, Berkeley CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,21]]},"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.jctb.2005.01.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"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.1137\/100799642"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4%3C213::AID-RSA3%3E3.0.CO;2-Y"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.93.4.1659"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-013-1391-z"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.37236\/2055"},{"key":"e_1_2_1_11_1","volume-title":"Infinite and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erd\u0151s on his 60th Birthday)","author":"Erd\u0151s Paul","year":"1975"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90040-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.57"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"David G. Harris and Aravind Srinivasan. 2014. A constructive algorithm for the Lov\u00e1sz local lemma on permutations. In SODA. SIAM 907--925.   David G. Harris and Aravind Srinivasan. 2014. A constructive algorithm for the Lov\u00e1sz local lemma on permutations. In SODA. SIAM 907--925.","DOI":"10.1137\/1.9781611973402.68"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.85"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.37236\/2319"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kashyap Kolipaka Mario Szegedy and Yixin Xu. 2012. A sharper local lemma with improved applications. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques Anupam Gupta Klaus Jansen Jos\u00e9 Rolim and Rocco Servedio (Eds.). Lecture Notes in Computer Science Vol. 7408. Springer Berlin 603--614. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-32512-0_51  Kashyap Kolipaka Mario Szegedy and Yixin Xu. 2012. A sharper local lemma with improved applications. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques Anupam Gupta Klaus Jansen Jos\u00e9 Rolim and Rocco Servedio (Eds.). Lecture Notes in Computer Science Vol. 7408. Springer Berlin 603--614. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-32512-0_51","DOI":"10.1007\/978-3-642-32512-0_51"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993669"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Linyuan Lu Austin Mohr and L\u00e1szl\u00f3 Sz\u00e9kely. 2013. Quest for negative dependency graphs. In Recent Advances in Harmonic Analysis and Applications. Springer 243--258.  Linyuan Lu Austin Mohr and L\u00e1szl\u00f3 Sz\u00e9kely. 2013. Quest for negative dependency graphs. In Recent Advances in Harmonic Analysis and Applications. Springer 243--258.","DOI":"10.1007\/978-1-4614-4565-4_21"},{"key":"e_1_2_1_21_1","unstructured":"Austin Mohr. 2013. Applications of the Lopsided Lov\u00e1sz Local Lemma Regarding Hypergraphs. Ph.D. Dissertation. University of South Carolina Columbia SC.  Austin Mohr. 2013. Applications of the Lopsided Lov\u00e1sz Local Lemma Regarding Hypergraphs. Ph.D. Dissertation. University of South Carolina Columbia SC."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536462"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185365"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20354"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/110828290"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579368"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"e_1_2_1_30_1","unstructured":"Aravind Srinivasan. 2008. Improved algorithmic versions of the Lov\u00e1sz local lemma. In SODA Shang-Hua Teng (Ed.). SIAM 611--620.   Aravind Srinivasan. 2008. Improved algorithmic versions of the Lov\u00e1sz local lemma. In SODA Shang-Hua Teng (Ed.). SIAM 611--620."},{"key":"e_1_2_1_31_1","volume-title":"CSR, Lecture Notes in Computer Science, Andrei A","author":"Szegedy Mario"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818352","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:39Z","timestamp":1750225419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,21]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1145\/2818352"],"URL":"https:\/\/doi.org\/10.1145\/2818352","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,21]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}