{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:30:54Z","timestamp":1787509854902,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":72,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897570","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T09:04:07Z","timestamp":1465549447000},"page":"479-488","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":80,"title":["A lower bound for the distributed Lov\u00e1sz local lemma"],"prefix":"10.1145","author":[{"given":"Sebastian","family":"Brandt","sequence":"first","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Orr","family":"Fischer","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juho","family":"Hirvonen","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barbara","family":"Keller","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tuomo","family":"Lempi\u00e4inen","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joel","family":"Rybicki","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[{"name":"Bitsplitters, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"ep(d + 1) < 1 O(log n log d) {11 19} epd 2 < 1 O(log n)  ep(d + 1) < 1 O(log n log d) {11 19} epd 2 < 1 O(log n)"},{"key":"e_1_3_2_1_2_1","unstructured":"pf (d) < 1 where f (d) exponential O(log n\/ log log n)  pf (d) < 1 where f (d) exponential O(log n\/ log log n)"},{"key":"e_1_3_2_1_3_1","unstructured":"pf (d) \u2264 1 for any f \u03a9(log \u2217 n)  pf (d) \u2264 1 for any f \u03a9(log \u2217 n)"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_3_2_1_5_1","series-title":"Lecture Notes in Computer Science","first-page":"239","volume-title":"Property Testing","author":"Alon N.","unstructured":"N. Alon . On constant time approximation of parameters of bounded degree graphs . In O. Goldreich, editor, Property Testing , volume 6390 of Lecture Notes in Computer Science , pages 234\u2013 239 . Springer, 2010. N. Alon. On constant time approximation of parameters of bounded degree graphs. In O. Goldreich, editor, Property Testing, volume 6390 of Lecture Notes in Computer Science, pages 234\u2013239. Springer, 2010."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"doi:10.1007\/978-3-642-16367-8 14.  doi:10.1007\/978-3-642-16367-8 14.","DOI":"10.1007\/978-3-642-16367-8"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02009-4","volume-title":"Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan &amp","author":"Barenboim L.","year":"2013","unstructured":"L. Barenboim and M. Elkin . Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan &amp ; Claypool , 2013 . L. Barenboim and M. Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool, 2013."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"doi:10.2200\/S00520ED1V01Y201307DCT011.  doi:10.2200\/S00520ED1V01Y201307DCT011.","DOI":"10.2200\/S00520ED1V01Y201307DCT011"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/12088848X.  doi:10.1137\/12088848X.","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"doi:10.1109\/FOCS.2012.60.  doi:10.1109\/FOCS.2012.60.","DOI":"10.1002\/nadc.201290404"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_3_2_1_15_1","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s B.","year":"1978","unstructured":"B. Bollob\u00e1s . Extremal Graph Theory . Academic Press , London , 1978 . B. Bollob\u00e1s. Extremal Graph Theory. Academic Press, London, 1978."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/100799642"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/100799642.  doi:10.1137\/100799642.","DOI":"10.1137\/100799642"},{"key":"e_1_3_2_1_18_1","volume-title":"February","author":"Chang Y.-J.","year":"2016","unstructured":"Y.-J. Chang , T. Kopelowitz , and S. Pettie . An exponential separation between randomized and deterministic complexity in the LOCAL model , February 2016 . Y.-J. Chang, T. Kopelowitz, and S. Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model, February 2016."},{"key":"e_1_3_2_1_19_1","unstructured":"arXiv:1602.08166.  arXiv:1602.08166."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611465"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/2611462.2611465.  doi:10.1145\/2611462.2611465.","DOI":"10.1145\/2611462.2611465"},{"key":"e_1_3_2_1_22_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_3_2_1_23_1","unstructured":"doi:10.1002\/1098-2418(200010\/12)17:3\/4<213:: AID-RSA3>3.0.CO;2-Y.  doi:10.1002\/1098-2418(200010\/12)17:3\/4<213:: AID-RSA3>3.0.CO;2-Y."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335310"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/335305.335310.  doi:10.1145\/335305.335310.","DOI":"10.1145\/335305.335310"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"doi:10.1007\/978-3-540-87779-0 6.  doi:10.1007\/978-3-540-87779-0 6.","DOI":"10.1007\/978-3-540-87779-0"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722155"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/1.9781611973730.26.  doi:10.1137\/1.9781611973730.26.","DOI":"10.1137\/1.9781611973730.26"},{"key":"e_1_3_2_1_31_1","volume-title":"Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 2(2):609\u2013627","author":"Lov\u00e1sz P.","year":"1975","unstructured":"P. Erd\u02dd os and L. Lov\u00e1sz . Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 2(2):609\u2013627 , 1975 . P. Erd\u02dd os and L. Lov\u00e1sz. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 2(2):609\u2013627, 1975."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554831"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/2554797.2554831. arXiv:arXiv:1304.1831.  doi:10.1145\/2554797.2554831. arXiv:arXiv:1304.1831.","DOI":"10.1145\/2554797.2554831"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528405"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/2528405. arXiv:1201.6675.  doi:10.1145\/2528405. arXiv:1201.6675.","DOI":"10.1145\/2528405"},{"key":"e_1_3_2_1_37_1","volume-title":"Distributed Computing","author":"G\u00f6\u00f6s M.","year":"2015","unstructured":"M. G\u00f6\u00f6s , J. Hirvonen , and J. Suomela . Linear-in-\u2206 lower bounds in the LOCAL model . Distributed Computing , 2015 . M. G\u00f6\u00f6s, J. Hirvonen, and J. Suomela. Linear-in-\u2206 lower bounds in the LOCAL model. Distributed Computing, 2015."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"doi:10.1007\/s00446-015-0245-8. arXiv:1304.1007.  doi:10.1007\/s00446-015-0245-8. arXiv:1304.1007.","DOI":"10.1007\/s00446-015-0245-8"},{"key":"e_1_3_2_1_39_1","volume-title":"September","author":"Haeupler B.","year":"2015","unstructured":"B. Haeupler and D. G. Harris . Improved bounds and parallel algorithms for the Lov\u00e1sz local lemma , September 2015 . B. Haeupler and D. G. Harris. Improved bounds and parallel algorithms for the Lov\u00e1sz local lemma, September 2015."},{"key":"e_1_3_2_1_40_1","unstructured":"arXiv:1509.06430.  arXiv:1509.06430."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/2049697.2049702. arXiv:arXiv:1001.1231v5.  doi:10.1145\/2049697.2049702. arXiv:arXiv:1001.1231v5.","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/1011767.1011811.  doi:10.1145\/1011767.1011811.","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109666"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/1109557.1109666.  doi:10.1145\/1109557.1109666.","DOI":"10.1145\/1109557.1109666"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050061"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"doi:10.1007\/s004930050061.  doi:10.1007\/s004930050061.","DOI":"10.1007\/s004930050061"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_27"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"doi:10.1007\/978-3-540-87779-0 27.  doi:10.1007\/978-3-540-87779-0 27.","DOI":"10.1007\/978-3-540-87779-0"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/0221015.  doi:10.1137\/0221015.","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/0215074.  doi:10.1137\/0215074.","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/276698.276866.  doi:10.1145\/276698.276866.","DOI":"10.1145\/276698.276866"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536462"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/1536414.1536462.  doi:10.1145\/1536414.1536462.","DOI":"10.1145\/1536414.1536462"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/1667053.1667060. arXiv:0903.0544.  doi:10.1145\/1667053.1667060. arXiv:0903.0544.","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/0404036.  doi:10.1137\/0404036.","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/S0097539793254571.  doi:10.1137\/S0097539793254571.","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579368"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434620"},{"key":"e_1_3_2_1_70_1","first-page":"620","volume-title":"Proc. 19h Annual ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Srinivasan A.","year":"2008","unstructured":"A. Srinivasan . Improved algorithmic versions of the Lov\u00e1sz local lemma . In Proc. 19h Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008 ), pages 611\u2013 620 . SIAM, 2008. A. Srinivasan. Improved algorithmic versions of the Lov\u00e1sz local lemma. In Proc. 19h Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pages 611\u2013620. SIAM, 2008."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431223"},{"key":"e_1_3_2_1_72_1","unstructured":"doi:10.1145\/2431211.2431223. http:\/\/www.cs.helsinki.fi\/local-survey\/. Introduction Distributed Lov\u00e1sz Local Lemma Main Result and Key Techniques Prior Work on LLL Prior Work on Other Lower Bounds Preliminaries Colourings Model of Computation Local Neighbourhoods Distributed Sinkless Orientation and Sinkless Colouring Distributed Lov\u00e1sz Local Lemma From LLL to Sinkless Orientation The Mutual Speedup Lemma From Sinkless Colouring to Sinkless Orientation From Sinkless Orientation Back to Sinkless Colouring The Speedup Lemma Lower Bounds Conclusions Acknowledgements References  doi:10.1145\/2431211.2431223. http:\/\/www.cs.helsinki.fi\/local-survey\/. Introduction Distributed Lov\u00e1sz Local Lemma Main Result and Key Techniques Prior Work on LLL Prior Work on Other Lower Bounds Preliminaries Colourings Model of Computation Local Neighbourhoods Distributed Sinkless Orientation and Sinkless Colouring Distributed Lov\u00e1sz Local Lemma From LLL to Sinkless Orientation The Mutual Speedup Lemma From Sinkless Colouring to Sinkless Orientation From Sinkless Orientation Back to Sinkless Colouring The Speedup Lemma Lower Bounds Conclusions Acknowledgements References"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897570","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897570","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:55:57Z","timestamp":1750208157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897570"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":72,"alternative-id":["10.1145\/2897518.2897570","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897570","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}