{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:55Z","timestamp":1750220335411,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":20,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF grants","award":["CCF-1814603, CCF-1910588"],"award-info":[{"award-number":["CCF-1814603, CCF-1910588"]}]},{"name":"NSF CAREER award","award":["CCF-1750808"],"award-info":[{"award-number":["CCF-1750808"]}]},{"name":"ERC grant agreement","award":["949272"],"award-info":[{"award-number":["949272"]}]},{"name":"Sloan Research Fellowship"},{"name":"Swiss National Foundation","award":["200021-184735"],"award-info":[{"award-number":["200021-184735"]}]},{"name":"NRF Fellowship for AI","award":["R-252-000-A33-133"],"award-info":[{"award-number":["R-252-000-A33-133"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538464","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"372-374","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver"],"prefix":"10.1145","author":[{"given":"Ioannis","family":"Anagnostides","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Lenzen","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbrucken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[{"name":"ETH Zurich & Carnegie Mellon University, Zurich & Pittsburgh, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Goran","family":"Zuzic","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Themis","family":"Gouleakis","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model. In 35th International Symposium on Distributed Computing, DISC 2021 (LIPIcs","volume":"19","author":"Anagnostides Ioannis","year":"2021","unstructured":"Ioannis Anagnostides and Themis Gouleakis . 2021 . Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model. In 35th International Symposium on Distributed Computing, DISC 2021 (LIPIcs , Vol. 209). Schloss Dagstuhl - Leibniz- Zentrum f\u00fcr Informatik, 5:1--5: 19 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.5 10.4230\/LIPIcs.DISC.2021.5 Ioannis Anagnostides and Themis Gouleakis. 2021. Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model. In 35th International Symposium on Distributed Computing, DISC 2021 (LIPIcs, Vol. 209). Schloss Dagstuhl - Leibniz- Zentrum f\u00fcr Informatik, 5:1--5:19. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.5"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323195"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.78"},{"key":"e_1_3_2_2_4_1","volume-title":"38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021","volume":"19","author":"Censor-Hillel Keren","year":"2021","unstructured":"Keren Censor-Hillel , Dean Leitersdorf , and Volodymyr Polosukhin . 2021 . Distance Computations in the Hybrid Network Model via Oracle Simulations . In 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 , March 16 --19 , 2021 (LIPIcs, Vol. 187). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 21:1--21: 19 . https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.21 10.4230\/LIPIcs.STACS.2021.21 Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. 2021. Distance Computations in the Hybrid Network Model via Oracle Simulations. In 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16--19, 2021 (LIPIcs, Vol. 187). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 21:1--21:19. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.21"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2016.05.009"},{"key":"e_1_3_2_2_6_1","unstructured":"Sam Coy Artur Czumaj Michael Feldmann Kristian Hinnenthal Fabian Kuhn Christian Scheideler Philipp Schneider and Martijn Struijs. 2022. Near-Shortest Path Routing in Hybrid Communication Networks. arXiv:2202.08008 [cs.DC]  Sam Coy Artur Czumaj Michael Feldmann Kristian Hinnenthal Fabian Kuhn Christian Scheideler Philipp Schneider and Martijn Struijs. 2022. Near-Shortest Path Routing in Hybrid Communication Networks. arXiv:2202.08008 [cs.DC]"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993686"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007407"},{"key":"e_1_3_2_2_9_1","volume-title":"Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs. In 24th International Conference on Principles of Distributed Systems, OPODIS 2020 (LIPIcs","volume":"16","author":"Feldmann Michael","year":"2020","unstructured":"Michael Feldmann , Kristian Hinnenthal , and Christian Scheideler . 2020 . Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs. In 24th International Conference on Principles of Distributed Systems, OPODIS 2020 (LIPIcs , Vol. 184). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 31:1--31: 16 . https: \/\/doi.org\/10.4230\/LIPIcs.OPODIS.2020.31 10.4230\/LIPIcs.OPODIS.2020.31 Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler. 2020. Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs. In 24th International Conference on Principles of Distributed Systems, OPODIS 2020 (LIPIcs, Vol. 184). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 31:1--31:16. https: \/\/doi.org\/10.4230\/LIPIcs.OPODIS.2020.31"},{"key":"e_1_3_2_2_10_1","volume-title":"Minor Sparsifiers and the Distributed Laplacian Paradigm. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021","author":"Forster Sebastian","year":"2021","unstructured":"Sebastian Forster , Gramoz Goranci , Yang P. Liu , Richard Peng , Xiaorui Sun , and Mingquan Ye . 2021 . Minor Sparsifiers and the Distributed Laplacian Paradigm. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 . IEEE, 989--999. https:\/\/doi.org\/10.1109\/FOCS52979.2021.00099 10.1109\/FOCS52979.2021.00099 Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. 2021. Minor Sparsifiers and the Distributed Laplacian Paradigm. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021. IEEE, 989--999. https:\/\/doi.org\/10.1109\/FOCS52979.2021.00099"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_2_12_1","volume-title":"Oblivious Routing, and Universally-Optimal Distributed Algorithms. arXiv preprint","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari , Bernhard Haeupler , and Harald R\u00e4cke . 2021. Hop-Constrained Expander Decompositions , Oblivious Routing, and Universally-Optimal Distributed Algorithms. arXiv preprint ( 2021 ). Mohsen Ghaffari, Bernhard Haeupler, and Harald R\u00e4cke. 2021. Hop-Constrained Expander Decompositions, Oblivious Routing, and Universally-Optimal Distributed Algorithms. arXiv preprint (2021)."},{"key":"e_1_3_2_2_13_1","volume-title":"Time-Optimal Construction of Overlay Networks. In PODC '21: ACM Symposium on Principles of Distributed Computing. ACM, 457--468","author":"G\u00f6tte Thorsten","year":"2021","unstructured":"Thorsten G\u00f6tte , Kristian Hinnenthal , Christian Scheideler , and JulianWerthmann. 2021 . Time-Optimal Construction of Overlay Networks. In PODC '21: ACM Symposium on Principles of Distributed Computing. ACM, 457--468 . https:\/\/doi. org\/10.1145\/3465084.3467932 Thorsten G\u00f6tte, Kristian Hinnenthal, Christian Scheideler, and JulianWerthmann. 2021. Time-Optimal Construction of Overlay Networks. In PODC '21: ACM Symposium on Principles of Distributed Computing. ACM, 457--468. https:\/\/doi. org\/10.1145\/3465084.3467932"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451081"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.icte.2017.08.002"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405719"},{"key":"e_1_3_2_2_17_1","unstructured":"Fabian Kuhn and Philipp Schneider. 2022. Routing Schemes and Distance Oracles in the Hybrid Model. arXiv:2202.06624 [cs.DC]  Fabian Kuhn and Philipp Schneider. 2022. Routing Schemes and Distance Oracles in the Hybrid Model. arXiv:2202.06624 [cs.DC]"},{"key":"e_1_3_2_2_18_1","volume-title":"40th Annual Symposium on Foundations of Computer Science. 253--261","author":"Peleg D.","year":"1999","unstructured":"D. Peleg and V. Rubinovich . 1999. A near-tight lower bound on the time complexity of distributed MST construction . In 40th Annual Symposium on Foundations of Computer Science. 253--261 . https:\/\/doi.org\/10.1109\/SFFCS. 1999 .814597 10.1109\/SFFCS.1999.814597 D. Peleg and V. Rubinovich. 1999. A near-tight lower bound on the time complexity of distributed MST construction. In 40th Annual Symposium on Foundations of Computer Science. 253--261. https:\/\/doi.org\/10.1109\/SFFCS.1999.814597"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_2_20_1","volume-title":"Proceedings of the ACM SIGCOMM 2010 Conference (SIGCOMM '10)","author":"Andersen David G.","year":"2010","unstructured":"GuohuiWang, David G. Andersen , Michael Kaminsky , Konstantina Papagiannaki , T.S. Eugene Ng , Michael Kozuch , and Michael Ryan . 2010 . C-Through: Part-Time Optics in Data Centers . In Proceedings of the ACM SIGCOMM 2010 Conference (SIGCOMM '10) . Association for Computing Machinery, 327--338. https:\/\/doi. org\/10.1145\/ 1851182.1851222 GuohuiWang, David G. Andersen, Michael Kaminsky, Konstantina Papagiannaki, T.S. Eugene Ng, Michael Kozuch, and Michael Ryan. 2010. C-Through: Part-Time Optics in Data Centers. In Proceedings of the ACM SIGCOMM 2010 Conference (SIGCOMM '10). Association for Computing Machinery, 327--338. https:\/\/doi. org\/10.1145\/1851182.1851222"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Salerno Italy","acronym":"PODC '22"},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538464","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538464","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:21Z","timestamp":1750191141000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":20,"alternative-id":["10.1145\/3519270.3538464","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538464","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}