{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:42Z","timestamp":1781078262888,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Institute for Advanced Study","award":["Fund for Math"],"award-info":[{"award-number":["Fund for Math"]}]},{"name":"National Science Foundation","award":["CCF- 1900460"],"award-info":[{"award-number":["CCF- 1900460"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,6]]},"DOI":"10.1145\/3350755.3400250","type":"proceedings-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T15:56:12Z","timestamp":1594310172000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Simple Local Computation Algorithms for the General Lov\u00e1sz Local Lemma"],"prefix":"10.1145","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[{"name":"National and Kapodistrian University of Athens, Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Themis","family":"Gouleakis","sequence":"additional","affiliation":[{"name":"Max-Planck-Institute for informatics, Saarbrucken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fotis","family":"Iliopoulos","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818352"},{"key":"e_1_3_2_1_2_1","unstructured":"Dimitris Achlioptas Fotis Iliopoulos and Vladimir Kolmogorov. A local lemma for focused stochastic algorithms. rm To appear in SIAM Journal on Computing. Preprint at arXiv:1805.02026.  Dimitris Achlioptas Fotis Iliopoulos and Vladimir Kolmogorov. A local lemma for focused stochastic algorithms. rm To appear in SIAM Journal on Computing. Preprint at arXiv:1805.02026."},{"key":"e_1_3_2_1_3_1","volume-title":"Beyond the Lov\u00e1sz local lemma: Point to set correlations and their algorithmic applications. rm To appear in Proceedings of IEEE FOCS","author":"Achlioptas Dimitris","year":"2019","unstructured":"Dimitris Achlioptas , Fotis Iliopoulos , and Alistair Sinclair . Beyond the Lov\u00e1sz local lemma: Point to set correlations and their algorithmic applications. rm To appear in Proceedings of IEEE FOCS , 2019 . Preprint at arXiv:1805.02026. URL : http:\/\/arxiv.org\/abs\/1805.02026, href http:\/\/arxiv.org\/abs\/1805.02026 patharXiv:1805.02026 . Dimitris Achlioptas, Fotis Iliopoulos, and Alistair Sinclair. Beyond the Lov\u00e1sz local lemma: Point to set correlations and their algorithmic applications. rm To appear in Proceedings of IEEE FOCS, 2019. Preprint at arXiv:1805.02026. URL: http:\/\/arxiv.org\/abs\/1805.02026, href http:\/\/arxiv.org\/abs\/1805.02026 patharXiv:1805.02026 ."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9075-9"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095205"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/100808186"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000253"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100225"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175473"},{"key":"e_1_3_2_1_12_1","first-page":"134","volume-title":"ACM Symposium on Principles of Distributed Computing, PODC '14","author":"Chung Kai-Min","year":"2014","unstructured":"Kai-Min Chung , Seth Pettie , and Hsin-Hao Su . Distributed algorithms for the Lov\u00e1 sz local lemma and graph coloring. In Magn\u00fa s M. Halld\u00f3 rsson and Shlomi Dolev, editors , ACM Symposium on Principles of Distributed Computing, PODC '14 , Paris, France, July 15--18 , 2014 , pages 134 -- 143 . ACM, 2014. URL: http:\/\/doi.acm.org\/10.1145\/2611462.2611465, href http:\/\/dx.doi.org\/10.1145\/2611462.2611465 pathdoi:10.1145\/2611462.2611465 . 10.1145\/2611462.2611465 Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the Lov\u00e1 sz local lemma and graph coloring. In Magn\u00fa s M. Halld\u00f3 rsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15--18, 2014, pages 134--143. ACM, 2014. URL: http:\/\/doi.acm.org\/10.1145\/2611462.2611465, href http:\/\/dx.doi.org\/10.1145\/2611462.2611465 pathdoi:10.1145\/2611462.2611465 ."},{"key":"e_1_3_2_1_13_1","first-page":"30","volume-title":"Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Czumaj Artur","year":"2000","unstructured":"Artur Czumaj and Christian Scheideler . Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lov\u00e1sz local lemma . In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms ( San Francisco, CA , 2000 ), pages 30 -- 39 , 2000. Artur Czumaj and Christian Scheideler. Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lov\u00e1sz local lemma. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), pages 30--39, 2000."},{"key":"e_1_3_2_1_14_1","first-page":"609","volume-title":"Keszthely, 1973; dedicated to P. ErdH os on his 60th birthday)","author":"L\u00e1szl\u00f3 Lov\u00e1sz Paul","unstructured":"Paul ErdHo s and L\u00e1szl\u00f3 Lov\u00e1sz . Problems and results on $3$-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq ., Keszthely, 1973; dedicated to P. ErdH os on his 60th birthday) , Vol. II , pages 609 -- 627 . Colloq. Math. Soc. J\u00e1nos Bolyai , Vol. 10. North-Holland, Amsterdam, 1975. Paul ErdHo s and L\u00e1szl\u00f3 Lov\u00e1sz. Problems and results on $3$-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. ErdH os on his 60th birthday), Vol. II, pages 609--627. Colloq. Math. Soc. J\u00e1nos Bolyai, Vol. 10. North-Holland, Amsterdam, 1975."},{"key":"e_1_3_2_1_15_1","volume-title":"Lopsided Lov\u00e1sz local lemma and latin transversals. Discrete Applied Mathematics, 30(2--3):151--154","author":"Erd\u00f6s Paul","year":"1991","unstructured":"Paul Erd\u00f6s and Joel Spencer . Lopsided Lov\u00e1sz local lemma and latin transversals. Discrete Applied Mathematics, 30(2--3):151--154 , 1991 . Paul Erd\u00f6s and Joel Spencer. Lopsided Lov\u00e1sz local lemma and latin transversals. Discrete Applied Mathematics, 30(2--3):151--154, 1991."},{"key":"e_1_3_2_1_16_1","volume-title":"Sublogarithmic distributed algorithms for lov$backslash$'asz local lemma, and the complexity hierarchy. arXiv preprint arXiv:1705.04840","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer and Mohsen Ghaffari . Sublogarithmic distributed algorithms for lov$backslash$'asz local lemma, and the complexity hierarchy. arXiv preprint arXiv:1705.04840 , 2017 . Manuela Fischer and Mohsen Ghaffari. Sublogarithmic distributed algorithms for lov$backslash$'asz local lemma, and the complexity hierarchy. arXiv preprint arXiv:1705.04840, 2017."},{"key":"e_1_3_2_1_17_1","first-page":"664","volume-title":"The local lemma is tight for SAT","author":"Gebauer Heidi","year":"2011","unstructured":"Heidi Gebauer , Tibor Szab\u00f3 , and G\u00e1bor Tardos . The local lemma is tight for SAT . In Dana Randall, editor, SODA, pages 664 -- 674 . SIAM , 2011 . Heidi Gebauer, Tibor Szab\u00f3, and G\u00e1bor Tardos. The local lemma is tight for SAT. In Dana Randall, editor, SODA, pages 664--674. SIAM, 2011."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_20_1","first-page":"907","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"David","year":"2014","unstructured":"David G. Harris and Aravind Srinivasan. A constructive algorithm for the Lov\u00e1 sz local lemma on permutations . In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 , Portland, Oregon, USA , January 5--7, 2014, pages 907 -- 925 . SIAM , 2014. URL: http:\/\/dx.doi.org\/10.1137\/1.9781611973402.68, href http:\/\/dx.doi.org\/10.1137\/1.9781611973402.68 pathdoi:10.1137\/1.9781611973402.68 . 10.1137\/1.9781611973402.68 David G. Harris and Aravind Srinivasan. A constructive algorithm for the Lov\u00e1 sz local lemma on permutations. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5--7, 2014, pages 907--925. SIAM, 2014. URL: http:\/\/dx.doi.org\/10.1137\/1.9781611973402.68, href http:\/\/dx.doi.org\/10.1137\/1.9781611973402.68 pathdoi:10.1137\/1.9781611973402.68 ."},{"key":"e_1_3_2_1_21_1","first-page":"1327","volume-title":"IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015","author":"Nicholas J.","year":"2015","unstructured":"Nicholas J. A. Harvey and Jan Vondr\u00e1 k. An algorithmic proof of the Lov\u00e1sz local lemma via resampling oracles. In Venkatesan Guruswami, editor , IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 , Berkeley, CA, USA, 17- -20 October , 2015 , pages 1327 -- 1346 . IEEE Computer Society, 2015. URL: http:\/\/dx.doi.org\/10.1109\/FOCS.2015.85, href http:\/\/dx.doi.org\/10.1109\/FOCS.2015.85 pathdoi:10.1109\/FOCS.2015.85 . 10.1109\/FOCS.2015.85 Nicholas J. A. Harvey and Jan Vondr\u00e1 k. An algorithmic proof of the Lov\u00e1sz local lemma via resampling oracles. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17--20 October, 2015, pages 1327--1346. IEEE Computer Society, 2015. URL: http:\/\/dx.doi.org\/10.1109\/FOCS.2015.85, href http:\/\/dx.doi.org\/10.1109\/FOCS.2015.85 pathdoi:10.1109\/FOCS.2015.85 ."},{"key":"e_1_3_2_1_22_1","volume-title":"Local computation mechanism design. ACM Transactions on Economics and Computation (TEAC), 4(4):21","author":"Hassidim Avinatan","year":"2016","unstructured":"Avinatan Hassidim , Yishay Mansour , and Shai Vardi . Local computation mechanism design. ACM Transactions on Economics and Computation (TEAC), 4(4):21 , 2016 . Avinatan Hassidim, Yishay Mansour, and Shai Vardi. Local computation mechanism design. ACM Transactions on Economics and Computation (TEAC), 4(4):21, 2016."},{"key":"e_1_3_2_1_23_1","unstructured":"Fotis\n      Iliopoulos\n    .\n  Commutative algorithms approximate the lll-distribution\n  . In Eric Blais Klaus Jansen Jos\u00e9 D. P. Rolim and David Steurer editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM \n  2018 August 20--22 2018 - Princeton NJ USA volume \n  116\n   of \n  LIPIcs pages 44:\n  1\n  --\n  44\n  :20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2018. \n  URL\n  : https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.44 href http:\/\/dx.doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.44 pathdoi:10.4230\/LIPIcs.APPROX-RANDOM.2018.44 .    10.4230\/LIPIcs.APPROX-RANDOM.2018.44\nFotis Iliopoulos. Commutative algorithms approximate the lll-distribution. In Eric Blais Klaus Jansen Jos\u00e9 D. P. Rolim and David Steurer editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2018 August 20--22 2018 - Princeton NJ USA volume 116 of LIPIcs pages 44:1--44:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2018. URL: https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.44 href http:\/\/dx.doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.44 pathdoi:10.4230\/LIPIcs.APPROX-RANDOM.2018.44 ."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.13"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.88"},{"key":"e_1_3_2_1_26_1","unstructured":"Reut\n      Levi Dana\n      Ron and \n      Ronitt\n      Rubinfeld\n    .\n  Local algorithms for sparse spanning graphs\n  . In Klaus Jansen Jos\u00e9 D. P. Rolim Nikhil R. Devanur and Cristopher Moore editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM \n  2014 September 4--6 2014 Barcelona Spain volume \n  28\n   of \n  LIPIcs pages \n  826\n  --\n  842\n  . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014. \n  URL\n  : https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2014.826 href http:\/\/dx.doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2014.826 pathdoi:10.4230\/LIPIcs.APPROX-RANDOM.2014.826 .    10.4230\/LIPIcs.APPROX-RANDOM.2014.826\nReut Levi Dana Ron and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. In Klaus Jansen Jos\u00e9 D. P. Rolim Nikhil R. Devanur and Cristopher Moore editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2014 September 4--6 2014 Barcelona Spain volume 28 of LIPIcs pages 826--842. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2014. URL: https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2014.826 href http:\/\/dx.doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2014.826 pathdoi:10.4230\/LIPIcs.APPROX-RANDOM.2014.826 ."},{"key":"e_1_3_2_1_27_1","unstructured":"Reut\n      Levi Dana\n      Ron and \n      Ronitt\n      Rubinfeld\n    .\n  A local algorithm for constructing spanners in minor-free graphs\n  . In Klaus Jansen Claire Mathieu Jos\u00e9 D. P. Rolim and Chris Umans editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM \n  2016 September 7--9 2016 Paris France volume \n  60\n   of \n  LIPIcs pages 38:\n  1\n  --\n  38\n  :15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2016. \n  URL\n  : https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.38 href http:\/\/dx.doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.38 pathdoi:10.4230\/LIPIcs.APPROX-RANDOM.2016.38 .    10.4230\/LIPIcs.APPROX-RANDOM.2016.38\nReut Levi Dana Ron and Ronitt Rubinfeld. A local algorithm for constructing spanners in minor-free graphs. In Klaus Jansen Claire Mathieu Jos\u00e9 D. P. Rolim and Chris Umans editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM 2016 September 7--9 2016 Paris France volume 60 of LIPIcs pages 38:1--38:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2016. URL: https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.38 href http:\/\/dx.doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.38 pathdoi:10.4230\/LIPIcs.APPROX-RANDOM.2016.38 ."},{"key":"e_1_3_2_1_28_1","unstructured":"Yishay\n      Mansour Aviad\n      Rubinstein Shai\n      Vardi and \n      Ning\n      Xie\n    .\n  Converting online algorithms to local computation algorithms\n  . In Artur Czumaj Kurt Mehlhorn Andrew M. Pitts and Roger Wattenhofer editors Automata Languages and Programming - 39th International Colloquium ICALP \n  2012 Warwick UK July 9--13 2012 Proceedings Part I volume \n  7391\n   of \n  Lecture Notes in Computer Science pages \n  653\n  --\n  664\n  . \n  Springer 2012. URL: https:\/\/doi.org\/10.1007\/978--3--642--31594--7_55 href http:\/\/dx.doi.org\/10.1007\/978--3--642--31594--7_55 pathdoi:10.1007\/978--3--642--31594--7_55 .    10.1007\/978--3--642--31594--7_55\nYishay Mansour Aviad Rubinstein Shai Vardi and Ning Xie. Converting online algorithms to local computation algorithms. In Artur Czumaj Kurt Mehlhorn Andrew M. Pitts and Roger Wattenhofer editors Automata Languages and Programming - 39th International Colloquium ICALP 2012 Warwick UK July 9--13 2012 Proceedings Part I volume 7391 of Lecture Notes in Computer Science pages 653--664. Springer 2012. URL: https:\/\/doi.org\/10.1007\/978--3--642--31594--7_55 href http:\/\/dx.doi.org\/10.1007\/978--3--642--31594--7_55 pathdoi:10.1007\/978--3--642--31594--7_55 ."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_19"},{"issue":"2","key":"e_1_3_2_1_30_1","first-page":"103","article-title":"A bound on the strong chromatic index of a graph. journal of combinatorial theory","volume":"69","author":"Molloy Michael","year":"1997","unstructured":"Michael Molloy and Bruce Reed . A bound on the strong chromatic index of a graph. journal of combinatorial theory , Series B , 69 ( 2 ): 103 -- 109 , 1997 . Michael Molloy and Bruce Reed. A bound on the strong chromatic index of a graph. journal of combinatorial theory, Series B, 69(2):103--109, 1997.","journal-title":"Series B"},{"key":"e_1_3_2_1_31_1","volume-title":"STOC '98","author":"Molloy Michael","year":"1999","unstructured":"Michael Molloy and Bruce Reed . Further algorithmic aspects of the local lemma . In STOC '98 ( Dallas, TX), pages 524--529. ACM, New York , 1999 . Michael Molloy and Bruce Reed. Further algorithmic aspects of the local lemma. In STOC '98 (Dallas, TX), pages 524--529. ACM, New York, 1999."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536462"},{"key":"e_1_3_2_1_34_1","first-page":"15","article-title":"A constructive proof of the general Lov\u00e1sz local lemma. J. ACM, 57(2)","volume":"11","author":"Moser Robin A.","year":"2010","unstructured":"Robin A. Moser and G\u00e1bor Tardos . A constructive proof of the general Lov\u00e1sz local lemma. J. ACM, 57(2) : Art. 11 , 15 , 2010 . URL: http:\/\/dx.doi.org\/10.1145\/1667053.1667060, href http:\/\/dx.doi.org\/10.1145\/1667053.1667060 pathdoi:10.1145\/1667053.1667060 . 10.1145\/1667053.1667060 Robin A. Moser and G\u00e1bor Tardos. A constructive proof of the general Lov\u00e1sz local lemma. J. ACM, 57(2):Art. 11, 15, 2010. URL: http:\/\/dx.doi.org\/10.1145\/1667053.1667060, href http:\/\/dx.doi.org\/10.1145\/1667053.1667060 pathdoi:10.1145\/1667053.1667060 .","journal-title":"Art."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185365"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.05.007"},{"key":"e_1_3_2_1_38_1","first-page":"223","volume-title":"Proceedings","author":"Rubinfeld Ronitt","year":"2011","unstructured":"Ronitt Rubinfeld , Gil Tamir , Shai Vardi , and Ning Xie . Fast local computation algorithms. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7--9, 2011 . Proceedings , pages 223 -- 238 . Tsinghua University Press , 2011 . URL: http:\/\/conference.itcs.tsinghua.edu.cn\/ICS2011\/content\/papers\/36.html. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7--9, 2011. Proceedings, pages 223--238. Tsinghua University Press, 2011. URL: http:\/\/conference.itcs.tsinghua.edu.cn\/ICS2011\/content\/papers\/36.html."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/080728561"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579368"},{"key":"e_1_3_2_1_41_1","unstructured":"Joel Spencer. Needles in exponential haystacks ii. URL: http:\/\/www.math.cornell.edu\/ cpss\/2012\/cornell12lec2.pdf.  Joel Spencer. Needles in exponential haystacks ii. URL: http:\/\/www.math.cornell.edu\/ cpss\/2012\/cornell12lec2.pdf."},{"key":"e_1_3_2_1_42_1","first-page":"611","volume-title":"Improved algorithmic versions of the Lov\u00e1sz local lemma","author":"Srinivasan Aravind","year":"2008","unstructured":"Aravind Srinivasan . Improved algorithmic versions of the Lov\u00e1sz local lemma . In Shang-Hua Teng, editor, SODA, pages 611 -- 620 . SIAM , 2008 . URL: http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347150. Aravind Srinivasan. Improved algorithmic versions of the Lov\u00e1sz local lemma. In Shang-Hua Teng, editor, SODA, pages 611--620. SIAM, 2008. URL: http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347150."},{"key":"e_1_3_2_1_43_1","volume-title":"Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):24","author":"Suomela Jukka","year":"2013","unstructured":"Jukka Suomela . Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):24 , 2013 . Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):24, 2013."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"}],"event":{"name":"SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures","location":"Virtual Event USA","acronym":"SPAA '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400250","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3350755.3400250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:35Z","timestamp":1750202015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3350755.3400250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":44,"alternative-id":["10.1145\/3350755.3400250","10.1145\/3350755"],"URL":"https:\/\/doi.org\/10.1145\/3350755.3400250","relation":{},"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2020-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}