{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T07:03:52Z","timestamp":1756191832286,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1910588, NSF CCF-1812919, CCF-1814603, CCF-1618280, CCF-1527110,CAREER award CCF-1750808"],"award-info":[{"award-number":["CCF-1910588, NSF CCF-1812919, CCF-1814603, CCF-1618280, CCF-1527110,CAREER award CCF-1750808"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Sloan Research Fellowship"},{"name":"Swiss National Foundation","award":["project grant 200021-184735"],"award-info":[{"award-number":["project grant 200021-184735"]}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000141912550"],"award-info":[{"award-number":["N000141912550"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451081","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1166-1179","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Universally-optimal distributed algorithms for known topologies"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3381-0459","authenticated-orcid":false,"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA \/ ETH Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1896-2948","authenticated-orcid":false,"given":"David","family":"Wajc","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9322-6329","authenticated-orcid":false,"given":"Goran","family":"Zuzic","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Smaller cuts, higher lower bounds. arXiv preprint arXiv:1901.01630","author":"Abboud Amir","year":"2019","unstructured":"Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. arXiv preprint arXiv:1901.01630, 2019."},{"key":"e_1_3_2_1_2_1","volume-title":"Instance-optimal geometric algorithms. Journal of the ACM (JACM), 64 (1): 1\u201338","author":"Afshani Peyman","year":"2017","unstructured":"Peyman Afshani, J\u00e9r\u00e9my Barbay, and Timothy M Chan. Instance-optimal geometric algorithms. Journal of the ACM (JACM), 64 (1): 1\u201338, 2017."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28421"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC)","author":"Becker Ruben","year":"2017","unstructured":"Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In Proceedings of the 31st International Symposium on Distributed Computing (DISC), 2017."},{"key":"e_1_3_2_1_5_1","volume-title":"Online computation and competitive analysis. cambridge university press","author":"Borodin Allan","year":"2005","unstructured":"Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. cambridge university press, 2005."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_3_2_1_7_1","first-page":"18","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Chuzhoy Julia","year":"2020","unstructured":"Julia Chuzhoy, Merav Parter, and Zihan Tan. On packing low-diameter spanning trees. In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), pages 33:1\u201333:18, 2020."},{"key":"e_1_3_2_1_8_1","series-title":"SIAM Journal on Computing (SICOMP), 41 (5): 1235\u20131265","volume-title":"Distributed verification and hardness of distributed approximation","author":"Sarma Atish Das","year":"2012","unstructured":"Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing (SICOMP), 41 (5): 1235\u20131265, 2012."},{"key":"e_1_3_2_1_9_1","first-page":"2021","volume-title":"Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC)","author":"Dory Michal","unstructured":"Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Distributed weighted min-cut in nearly-optimal time. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), page To appear, 2021."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-04-0.50013-2"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.07.002"},{"key":"e_1_3_2_1_12_1","series-title":"SIAM Journal on Computing (SICOMP), 36 (2): 433\u2013456","volume-title":"An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem","author":"Elkin Michael","year":"2006","unstructured":"Michael Elkin. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM Journal on Computing (SICOMP), 36 (2): 433\u2013456, 2006."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055452"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087823"},{"key":"e_1_3_2_1_15_1","volume-title":"Optimal aggregation algorithms for middleware. Journal of computer and system sciences, 66 (4): 614\u2013656","author":"Fagin Ronald","year":"2003","unstructured":"Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. Journal of computer and system sciences, 66 (4): 614\u2013656, 2003."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737382"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331581"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.91"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"e_1_3_2_1_20_1","first-page":"668","volume-title":"Proceedings of the 34th Symposium on Foundations of Computer Science (FOCS)","author":"Garay Juan A","year":"1993","unstructured":"Juan A Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. In Proceedings of the 34th Symposium on Foundations of Computer Science (FOCS), pages 659\u2013668, 1993."},{"key":"e_1_3_2_1_21_1","series-title":"SIAM Journal on Computing (SICOMP), 27 (1): 302\u2013316","volume-title":"A sublinear time distributed algorithm for minimum-weight spanning trees","author":"Garay Juan A","year":"1998","unstructured":"Juan A Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM Journal on Computing (SICOMP), 27 (1): 302\u2013316, 1998."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_51"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_1_24_1","first-page":"16","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC)","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Jason Li. New distributed algorithms in almost mixing time via transformations from parallel algorithms. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 31:1\u201331:16, 2018."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933103"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC), 91: 21","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari and Merav Parter. Near-optimal distributed DFS in planar graphs. Proceedings of the 31st International Symposium on Distributed Computing (DISC), 91: 21, 2017."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767440"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087827"},{"key":"e_1_3_2_1_29_1","volume-title":"Hop-constrained oblivious routing. page To appear","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic. Hop-constrained oblivious routing. page To appear, 2021."},{"key":"e_1_3_2_1_30_1","first-page":"613","volume-title":"Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Gonzalez Joseph E","year":"2014","unstructured":"Joseph E Gonzalez, Reynold S Xin, Ankur Dave, Daniel Crankshaw, Michael J Franklin, and Ion Stoica. Graphx: Graph processing in a distributed dataflow framework. In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 599\u2013613, 2014."},{"key":"e_1_3_2_1_31_1","first-page":"14","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC)","author":"Haeupler Bernhard","year":"2018","unstructured":"Bernhard Haeupler and Jason Li. Faster distributed shortest path approximations via shortcuts. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 33:1\u201333:14, 2018."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933112"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212737"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212776"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00053"},{"key":"e_1_3_2_1_37_1","first-page":"2021","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Haeupler Bernhard","unstructured":"Bernhard Haeupler, D Ellis Hershkowitz, and David Wajc. Near-optimal schedules for simultaneous multicasts. In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP), page To appear, 2021."},{"key":"e_1_3_2_1_38_1","volume-title":"Universally-optimal distributed algorithms for known topologies. arXiv preprint arXiv:2104.03932","author":"Haeupler Bernhard","year":"2021","unstructured":"Bernhard Haeupler, David Wajc, and Goran Zuzic. Universally-optimal distributed algorithms for known topologies. arXiv preprint arXiv:2104.03932, 2021."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2777598.2777604"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767434"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC)","author":"Henzinger Monika","year":"2016","unstructured":"Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. An almost-tight distributed algorithm for computing single-source shortest paths. In Proceedings of the ACM Symposium on Theory of Computing (STOC), 2016."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332504"},{"key":"e_1_3_2_1_43_1","first-page":"179","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Huang C.","year":"2017","unstructured":"C. Huang, D. Nanongkai, and T. Saranurak. Distributed exact weighted all-pairs shortest paths in $\\tildeO(n^5\/4)$ rounds. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 168\u2013179, 2017."},{"key":"e_1_3_2_1_44_1","first-page":"2632","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Krzysztof Nowicki Tomasz","year":"2018","unstructured":"Tomasz Jurdzi\\'nski and Krzysztof Nowicki. MST in $O(1)$ rounds of congested clique. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2620\u20132632, 2018."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0047-8"},{"key":"e_1_3_2_1_46_1","first-page":"17","volume-title":"Proceedings of the 33rd International Symposium on Distributed Computing (DISC)","author":"Kitamura Naoki","year":"2019","unstructured":"Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, and Taisuke Izumi. Low-congestion shortcut and graph parameters. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC), pages 25:1\u201325:17, 2019."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0929"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767398"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484262"},{"key":"e_1_3_2_1_51_1","series-title":"SIAM Journal on Computing (SICOMP), 35 (1): 120\u2013131","volume-title":"MST construction in $O(\u0142og \u0142og n)$ communication rounds","author":"Lotker Zvi","year":"2005","unstructured":"Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. MST construction in $O(\u0142og \u0142og n)$ communication rounds. SIAM Journal on Computing (SICOMP), 35 (1): 120\u2013131, 2005."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0127-6"},{"key":"e_1_3_2_1_53_1","first-page":"146","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD)","author":"Malewicz Grzegorz","year":"2010","unstructured":"Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 135\u2013146, 2010."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_30"},{"issue":"1","key":"e_1_3_2_1_57_1","first-page":"3","article-title":"Otakar boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history","volume":"233","author":"Jaroslav","year":"2001","unstructured":"Jaroslav Ne\u0161et\\vril, Eva Milkov\u00e1, and Helena Ne\u0161et\\vrilov\u00e1. Otakar boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics, 233 (1): 3\u201336, 2001.","journal-title":"Discrete Mathematics"},{"key":"e_1_3_2_1_58_1","series-title":"SIAM review, 45 (2): 167\u2013256","volume-title":"The structure and function of complex networks","author":"Newman Mark EJ","year":"2003","unstructured":"Mark EJ Newman. The structure and function of complex networks. SIAM review, 45 (2): 167\u2013256, 2003."},{"key":"e_1_3_2_1_59_1","volume-title":"A deterministic algorithm for the mst problem in constant rounds of congested clique. page To appear","author":"Nowicki Krzysztof","year":"2021","unstructured":"Krzysztof Nowicki. A deterministic algorithm for the mst problem in constant rounds of congested clique. page To appear, 2021."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055449"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_62_1","volume-title":"May","author":"Peleg David","year":"2000","unstructured":"David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM Journal on Computing (SICOMP), 30 (5): 1427\u20131442, May 2000."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374415"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032036"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491185.2491198"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_67_1","volume-title":"Self-adjusting binary search trees. Journal of the ACM (JACM), 32 (3): 652\u2013686","author":"Sleator Daniel Dominic","year":"1985","unstructured":"Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32 (3): 652\u2013686, 1985."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897641"},{"key":"e_1_3_2_1_69_1","series-title":"SIAM Journal on Computing (SICOMP), 46 (1): 429\u2013455","volume-title":"An automatic inequality prover and instance optimal identity testing","author":"Valiant Gregory","year":"2017","unstructured":"Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing (SICOMP), 46 (1): 429\u2013455, 2017."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451081","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451081","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451081","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":69,"alternative-id":["10.1145\/3406325.3451081","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451081","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}