{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:45Z","timestamp":1750693425895,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,10,31]],"date-time":"2017-10-31T00:00:00Z","timestamp":1509408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1527110, CCF-1618280, CNS-1010789 and CCF-1422569"],"award-info":[{"award-number":["CCF-1527110, CCF-1618280, CNS-1010789 and CCF-1422569"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>\n            The Lov\u00e1sz Local Lemma (LLL) is a cornerstone principle in the probabilistic method of combinatorics, and a seminal algorithm of Moser and Tardos (2010) provides an efficient randomized algorithm to implement it. This can be parallelized to give an algorithm that uses polynomially many processors and runs in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time on an EREW PRAM, stemming from\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) adaptive computations of a maximal independent set (MIS). Chung et al. (2014) developed faster local and parallel algorithms, potentially running in time\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), but these algorithms require more stringent conditions than the LLL. We give a new parallel algorithm that works under essentially the same conditions as the original algorithm of Moser and Tardos but uses only a single MIS computation, thus running in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time on an EREW PRAM. This can be derandomized to give an NC algorithm running in time\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) as well, speeding up a previous NC LLL algorithm of Chandrasekaran et al. (2013). We also provide improved and tighter bounds on the runtimes of the sequential and parallel resampling-based algorithms originally developed by Moser and Tardos. These apply to any problem instance in which the tighter Shearer LLL criterion is satisfied.\n          <\/jats:p>","DOI":"10.1145\/3147211","type":"journal-article","created":{"date-parts":[[2017,12,4]],"date-time":"2017-12-04T19:18:27Z","timestamp":1512415107000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Parallel Algorithms and Concentration Bounds for the Lov\u00e1sz Local Lemma via Witness DAGs"],"prefix":"10.1145","volume":"13","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"School of Computer Science, Carnegie Mellon University"}]},{"given":"David G.","family":"Harris","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD"}]}],"member":"320","published-online":{"date-parts":[[2017,12,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818352"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000253"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/100799642"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0287-6"},{"key":"e_1_2_1_5_1","unstructured":"P. Erd\u0151s and L. Lov\u00e1sz. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal R. Rado and V. T. Sos eds. Infinite and Finite Sets II 607--726.  P. Erd\u0151s and L. Lov\u00e1sz. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal R. Rado and V. T. Sos eds. Infinite and Finite Sets II 607--726."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199808)13:1%3C1::AID-RSA1%3E3.0.CO;2-W"},{"key":"e_1_2_1_7_1","unstructured":"M. Fischer and M. Ghaffari. 2017. Sublogarithmic distributed algorithms for Lov\u00e1sz local lemma and the complexity hierarchy. arxiv:1705.04840 (2017).  M. Fischer and M. Ghaffari. 2017. Sublogarithmic distributed algorithms for Lov\u00e1sz local lemma and the complexity hierarchy. arxiv:1705.04840 (2017)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3015762"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039763"},{"key":"e_1_2_1_12_1","volume-title":"Parallel algorithms for the lopsided Lov\u00e1sz local lemma. arxiv:17.02547","author":"Harris D.","year":"2017","unstructured":"D. Harris . 2017. Parallel algorithms for the lopsided Lov\u00e1sz local lemma. arxiv:17.02547 ( 2017 ). D. Harris. 2017. Parallel algorithms for the lopsided Lov\u00e1sz local lemma. arxiv:17.02547 (2017)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.85"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993669"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_16_1","volume-title":"Derandomizing the Lov\u00e1sz Local Lemma more effectively. arxiv:0807.2120","author":"Moser R.","year":"2008","unstructured":"R. Moser . 2008. Derandomizing the Lov\u00e1sz Local Lemma more effectively. arxiv:0807.2120 ( 2008 ). R. Moser. 2008. Derandomizing the Lov\u00e1sz Local Lemma more effectively. arxiv:0807.2120 (2008)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579368"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3147211","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3147211","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3147211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:15Z","timestamp":1750212675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3147211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,31]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3147211"],"URL":"https:\/\/doi.org\/10.1145\/3147211","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2017,10,31]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}