{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T08:55:41Z","timestamp":1772268941714,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":19,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["336495 (ACDC)"],"award-info":[{"award-number":["336495 (ACDC)"]}]},{"name":"European Union's Horizon 2020","award":["755839"],"award-info":[{"award-number":["755839"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,16]]},"DOI":"10.1145\/3293611.3331636","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:21Z","timestamp":1563542241000},"page":"389-398","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Sharp Threshold Phenomenon for the Distributed Complexity of the Lov\u00e1sz Local Lemma"],"prefix":"10.1145","author":[{"given":"Sebastian","family":"Brandt","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Zurich, Switzerland"}]},{"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich and University of Freiburg, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331630"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004.Convex Optimization. CambridgeUniversity Press.   Stephen Boyd and Lieven Vandenberghe. 2004.Convex Optimization. CambridgeUniversity Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331636"},{"key":"e_1_3_2_1_6_1","volume-title":"An Exponential Separationbetween Randomized and Deterministic Complexity in the LOCAL Model. Inthe Proceedings of the Symposium on Foundations of Computer Science (FOCS).615--624","author":"Chang Yi-Jun","year":"2016"},{"key":"e_1_3_2_1_7_1","volume-title":"Inthe Proceedings of the Symposium on Foundations of Computer Science(FOCS). 156--167","author":"Chang Yi-Jun","year":"2017"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0287-6"},{"key":"e_1_3_2_1_9_1","volume-title":"IntheProceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 30--39","author":"Czumaj Artur","year":"2000"},{"key":"e_1_3_2_1_10_1","unstructured":"Paul Erd\u00f6s and L\u00e1szl\u00f3 Lov\u00e1sz. 1974. Problems and Results on 3-chromatic Hy-pergraphs and some Related Questions.Colloquia Mathematica Societatis J\u00e1nosBolyai(1974) 609--627.{11}Manuela Fischer and Mohsen Ghaffari. 2017. Sublogarithmic Distributed Algo-rithms for Lov\u00e1sz Local Lemma and the Complexity Hierarchy. Inthe Proceedingsof the 31st International Symposium on Distributed Computing (DISC). 18:1--18:16.  Paul Erd\u00f6s and L\u00e1szl\u00f3 Lov\u00e1sz. 1974. Problems and Results on 3-chromatic Hy-pergraphs and some Related Questions.Colloquia Mathematica Societatis J\u00e1nosBolyai(1974) 609--627.{11}Manuela Fischer and Mohsen Ghaffari. 2017. Sublogarithmic Distributed Algo-rithms for Lov\u00e1sz Local Lemma and the Complexity Hierarchy. Inthe Proceedingsof the 31st International Symposium on Distributed Computing (DISC). 18:1--18:16."},{"key":"e_1_3_2_1_11_1","unstructured":"Pierre Fraigniaud Marc Heinrich and Adrian Kosowski. 2016. Local ConflictColoring. Inthe Proceedings of the Symposium on Foundations of Computer Science(FOCS). 625--634.{13}Mohsen Ghaffari. 2016. An Improved Distributed Algorithm for Maximal Indepen-dent Set. Inthe Proceedings of the ACM-SIAM Symposium on Discrete Algorithms(SODA). 270--277.{14}Mohsen Ghaffari David G. Harris and Fabian Kuhn. 2018. On DerandomizingLocal Distributed Algorithms. Inthe Proceedings of the Symposium on Foundationsof Computer Science (FOCS). 662--673.  Pierre Fraigniaud Marc Heinrich and Adrian Kosowski. 2016. Local ConflictColoring. Inthe Proceedings of the Symposium on Foundations of Computer Science(FOCS). 625--634.{13}Mohsen Ghaffari. 2016. An Improved Distributed Algorithm for Maximal Indepen-dent Set. Inthe Proceedings of the ACM-SIAM Symposium on Discrete Algorithms(SODA). 270--277.{14}Mohsen Ghaffari David G. Harris and Fabian Kuhn. 2018. On DerandomizingLocal Distributed Algorithms. Inthe Proceedings of the Symposium on Foundationsof Computer Science (FOCS). 662--673."},{"key":"e_1_3_2_1_12_1","unstructured":"Mohsen Ghaffari Juho Hirvonen Fabian Kuhn Yannic Maus Jukka Suomela and Jara Uitto. 2017. Improved Distributed Degree Splitting and Edge Coloring.19:1--19:15.  Mohsen Ghaffari Juho Hirvonen Fabian Kuhn Yannic Maus Jukka Suomela and Jara Uitto. 2017. Improved Distributed Degree Splitting and Edge Coloring.19:1--19:15."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_14_1","volume-title":"InProc. 28th ACM-SIAM Symp. on Discrete Algorithms(SODA).","author":"Ghaffari Mohsen","year":"2017"},{"key":"e_1_3_2_1_15_1","unstructured":"David G. Harris. 2018. Distributed approximation algorithms for maximum match-ing in graphs and hypergraphs.CoRRabs\/1807.07645 (2018). arXiv:1807.07645http:\/\/arxiv.org\/abs\/1807.07645  David G. Harris. 2018. Distributed approximation algorithms for maximum match-ing in graphs and hypergraphs.CoRRabs\/1807.07645 (2018). arXiv:1807.07645http:\/\/arxiv.org\/abs\/1807.07645"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990290"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_3_2_1_19_1","volume-title":"Improved Algorithmic Versions of the Lov\u00e1sz LocalLemma. Inthe Proceedings of the ACM-SIAM Symposium on Discrete Algorithms(SODA). 611--620","author":"Srinivasan Aravind","year":"2008"}],"event":{"name":"PODC '19: ACM Symposium on Principles of Distributed Computing","location":"Toronto ON Canada","acronym":"PODC '19","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331636","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331636","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:26Z","timestamp":1750204466000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331636"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":19,"alternative-id":["10.1145\/3293611.3331636","10.1145\/3293611"],"URL":"https:\/\/doi.org\/10.1145\/3293611.3331636","relation":{},"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}