{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:15:44Z","timestamp":1787386544250,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384298","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"350-363","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":108,"title":["Polylogarithmic-time deterministic network decomposition and distributed derandomization"],"prefix":"10.1145","author":[{"given":"V\u00e1clav","family":"Rozho\u0148","sequence":"first","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0159"},{"key":"e_1_3_2_1_3_1","volume-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS). 364-369","author":"Awerbuch B.","unstructured":"B. Awerbuch , A. V. Goldberg , M. Luby , and S. A. Plotkin . 1989. Network Decomposition and Locality in Distributed Computation . In Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS). 364-369 . B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. 1989. Network Decomposition and Locality in Distributed Computation. In Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS). 364-369."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00037"},{"key":"e_1_3_2_1_5_1","volume-title":"Proc. 29th Symp. on Principles of Distributed Computing (PODC). 410-419","author":"Barenboim L.","unstructured":"L. Barenboim and M. Elkin . 2010. Deterministic Distributed Vertex Coloring in Polylogarithmic Time . In Proc. 29th Symp. on Principles of Distributed Computing (PODC). 410-419 . L. Barenboim and M. Elkin. 2010. Deterministic Distributed Vertex Coloring in Polylogarithmic Time. In Proc. 29th Symp. on Principles of Distributed Computing (PODC). 410-419."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers.  L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"L. Barenboim M. Elkin S. Pettie and J. Schneider. 2016. The Locality of Distributed Symmetry Breaking. J. ACM 63 ( 2016 ) 20 : 1-20 : 45. Issue 3.  L. Barenboim M. Elkin S. Pettie and J. Schneider. 2016. The Locality of Distributed Symmetry Breaking. J. ACM 63 ( 2016 ) 20 : 1-20 : 45. Issue 3.","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_9_1","volume-title":"31st International Symposium on Distributed Computing (DISC 2017 ). Schloss DagstuhlLeibniz-Zentrum fuer Informatik.","author":"Censor-Hillel Keren","year":"2017","unstructured":"Keren Censor-Hillel , Merav Parter , and Gregory Schwartzman . 2017 . Derandomizing Local Distributed Algorithms under Bandwidth Restrictions . In 31st International Symposium on Distributed Computing (DISC 2017 ). Schloss DagstuhlLeibniz-Zentrum fuer Informatik. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. 2017. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In 31st International Symposium on Distributed Computing (DISC 2017 ). Schloss DagstuhlLeibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331607"},{"key":"e_1_3_2_1_11_1","volume-title":"Proc. 50th ACM Symp. on Theory of Computing (STOC).","author":"Chang Y.-J.","unstructured":"Y.-J. Chang , W. Li , and S. Pettie . 2018. An Optimal Distributed (\u2206 + 1)-Coloring Algorithm? . In Proc. 50th ACM Symp. on Theory of Computing (STOC). Y.-J. Chang, W. Li, and S. Pettie. 2018. An Optimal Distributed (\u2206 + 1)-Coloring Algorithm?. In Proc. 50th ACM Symp. on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_12_1","volume-title":"Proc. 58th IEEE Symp. on Foundations of Computer Science (FOCS). 156-167","author":"Chang Y.-J.","unstructured":"Y.-J. Chang and S. Pettie . 2017. A Time Hierarchy Theorem for the LOCAL Model . In Proc. 58th IEEE Symp. on Foundations of Computer Science (FOCS). 156-167 . Y.-J. Chang and S. Pettie. 2017. A Time Hierarchy Theorem for the LOCAL Model. In Proc. 58th IEEE Symp. on Foundations of Computer Science (FOCS). 156-167."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Kai-Min Chung Seth Pettie and Hsin-Hao Su. 2017. Distributed algorithms for the Lov\u00e1sz local lemma and graph coloring. Distributed Computing 30 4 ( 2017 ) 261-280.  Kai-Min Chung Seth Pettie and Hsin-Hao Su. 2017. Distributed algorithms for the Lov\u00e1sz local lemma and graph coloring. Distributed Computing 30 4 ( 2017 ) 261-280.","DOI":"10.1007\/s00446-016-0287-6"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331626"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.07.002"},{"key":"e_1_3_2_1_16_1","volume-title":"Proc. 31st Symp. on Distributed Computing (DISC). 18 : 1-18 : 16","author":"Fischer M.","unstructured":"M. Fischer and M. Ghafari . 2017. Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local lemma, and the complexity hierarchy . In Proc. 31st Symp. on Distributed Computing (DISC). 18 : 1-18 : 16 . M. Fischer and M. Ghafari. 2017. Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local lemma, and the complexity hierarchy. In Proc. 31st Symp. on Distributed Computing (DISC). 18 : 1-18 : 16."},{"key":"e_1_3_2_1_17_1","volume-title":"Proc. 58th IEEE Symp. on Foundations of Computer Science (FOCS).","author":"Fischer M.","unstructured":"M. Fischer , M. Ghafari , and F. Kuhn . 2017. Deterministic Distributed EdgeColoring via Hypergraph Maximal Matching . In Proc. 58th IEEE Symp. on Foundations of Computer Science (FOCS). M. Fischer, M. Ghafari, and F. Kuhn. 2017. Deterministic Distributed EdgeColoring via Hypergraph Maximal Matching. In Proc. 58th IEEE Symp. on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_1_19_1","first-page":"662","article-title":"On derandomizing local distributed algorithms","author":"Ghafari M.","year":"2018","unstructured":"M. Ghafari , D. Harris , and F. Kuhn . 2018 . On derandomizing local distributed algorithms . In Proc. Foundations of Computer Science (FOCS). 662 - 673 . M. Ghafari, D. Harris, and F. Kuhn. 2018. On derandomizing local distributed algorithms. In Proc. Foundations of Computer Science (FOCS). 662-673.","journal-title":"Proc. Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_20_1","volume-title":"32nd International Symposium on Distributed Computing (DISC 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Ghafari Mohsen","year":"2018","unstructured":"Mohsen Ghafari and Fabian Kuhn . 2018 . Derandomizing distributed algorithms with small messages: Spanners and dominating set . In 32nd International Symposium on Distributed Computing (DISC 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Mohsen Ghafari and Fabian Kuhn. 2018. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In 32nd International Symposium on Distributed Computing (DISC 2018 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_21_1","volume-title":"Proc. 49th ACM Symp. on Theory of Computing (STOC). 784-797","author":"Ghafari M.","unstructured":"M. Ghafari , F. Kuhn , and Y. Maus . 2017. On the Complexity of Local Distributed Graph Problems . In Proc. 49th ACM Symp. on Theory of Computing (STOC). 784-797 . M. Ghafari, F. Kuhn, and Y. Maus. 2017. On the Complexity of Local Distributed Graph Problems. In Proc. 49th ACM Symp. on Theory of Computing (STOC). 784-797."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.166"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_2_1_25_1","volume-title":"Deterministic coloring algorithms in the LOCAL model. arXiv preprint arXiv","author":"Kowalski Dariusz","year":"1907","unstructured":"Dariusz Kowalski and Piotr Krysta . 31 July 2019. Deterministic coloring algorithms in the LOCAL model. arXiv preprint arXiv : 1907 . 12857 ( 31 July 2019 ). Dariusz Kowalski and Piotr Krysta. 31 July 2019. Deterministic coloring algorithms in the LOCAL model. arXiv preprint arXiv: 1907. 12857 ( 31 July 2019 )."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584032"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"N. Linial and M. Saks. 1993. Low Diameter Graph Decompositions. Combinatorica 13 4 ( 1993 ) 441-454.  N. Linial and M. Saks. 1993. Low Diameter Graph Decompositions. Combinatorica 13 4 ( 1993 ) 441-454.","DOI":"10.1007\/BF01303516"},{"key":"e_1_3_2_1_31_1","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 1966. On decomposition of graphs. Studia Sci. Math. Hungar 1 273 ( 1966 ) 238.  L\u00e1szl\u00f3 Lov\u00e1sz. 1966. On decomposition of graphs. Studia Sci. Math. Hungar 1 273 ( 1966 ) 238."},{"key":"e_1_3_2_1_32_1","series-title":"SIAM J. Comput. 15 ( 1986 ), 1036-1053","volume-title":"A Simple Parallel Algorithm for the Maximal Independent Set Problem","author":"Luby M.","unstructured":"M. Luby . 1986. A Simple Parallel Algorithm for the Maximal Independent Set Problem . SIAM J. Comput. 15 ( 1986 ), 1036-1053 . M. Luby. 1986. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15 ( 1986 ), 1036-1053."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_2_1_35_1","volume-title":"Proc. 24th ACM Symp. on Theory of Computing (STOC). 581-592","author":"Panconesi A.","unstructured":"A. Panconesi and A. Srinivasan . 1992. Improved distributed algorithms for coloring and network decomposition problems . In Proc. 24th ACM Symp. on Theory of Computing (STOC). 581-592 . A. Panconesi and A. Srinivasan. 1992. Improved distributed algorithms for coloring and network decomposition problems. In Proc. 24th ACM Symp. on Theory of Computing (STOC). 581-592."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.  D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.","DOI":"10.1137\/1.9780898719772"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384298","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384298","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384298"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":36,"alternative-id":["10.1145\/3357713.3384298","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384298","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}