{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:35:18Z","timestamp":1782970518106,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":44,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P 32863-N"],"award-info":[{"award-number":["P 32863-N"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["947702"],"award-info":[{"award-number":["947702"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538436","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"335-344","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["The Laplacian Paradigm in the Broadcast Congested Clique"],"prefix":"10.1145","author":[{"given":"Sebastian","family":"Forster","sequence":"first","affiliation":[{"name":"University of Salzburg, Salzburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tijn","family":"de Vos","sequence":"additional","affiliation":[{"name":"University of Salzburg, Salzburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_3_2_2_2_1","volume-title":"Accelerated Distributed Laplacian Solvers via Shortcuts. CoRR abs\/2109.05151","author":"Anagnostides Ioannis","year":"2021","unstructured":"Ioannis Anagnostides , Themis Gouleakis , and Christoph Lenzen . 2021. Accelerated Distributed Laplacian Solvers via Shortcuts. CoRR abs\/2109.05151 ( 2021 ). arXiv:2109.05151 Ioannis Anagnostides, Themis Gouleakis, and Christoph Lenzen. 2021. Accelerated Distributed Laplacian Solvers via Shortcuts. CoRR abs\/2109.05151 (2021). arXiv:2109.05151"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00065"},{"key":"e_1_3_2_2_4_1","volume-title":"Iterative solution methods","author":"Axelsson Owe","unstructured":"Owe Axelsson . 1996. Iterative solution methods . Cambridge university press . Owe Axelsson. 1996. Iterative solution methods. Cambridge university press."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00059"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1233534"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1286955"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00380-5"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0270-2"},{"key":"e_1_3_2_2_11_1","volume-title":"Single-Source Shortest Paths in the CONGEST Model with Improved Bound. In In Proc. of the ACM Symposium on Principles of Distributed Computing (PODC","author":"Chechik Shiri","year":"2020","unstructured":"Shiri Chechik and Doron Mukhtar . 2020 . Single-Source Shortest Paths in the CONGEST Model with Improved Bound. In In Proc. of the ACM Symposium on Principles of Distributed Computing (PODC 2020). 464--473. https:\/\/doi.org\/10. 1145\/3382734.3405729 Shiri Chechik and Doron Mukhtar. 2020. Single-Source Shortest Paths in the CONGEST Model with Improved Bound. In In Proc. of the ACM Symposium on Principles of Distributed Computing (PODC 2020). 464--473. https:\/\/doi.org\/10. 1145\/3382734.3405729"},{"key":"e_1_3_2_2_12_1","volume-title":"Maximilian Probst Gutenberg, and Sushant Sachdeva","author":"Chen Li","year":"2022","unstructured":"Li Chen , Rasmus Kyng , Yang P. Liu , Richard Peng , Maximilian Probst Gutenberg, and Sushant Sachdeva . 2022 . Maximum Flow and Minimum-Cost Flow in Almost- Linear Time. CoRR abs\/2203.00671 (2022). arXiv:2203.00671 Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2022. Maximum Flow and Minimum-Cost Flow in Almost- Linear Time. CoRR abs\/2203.00671 (2022). arXiv:2203.00671"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688113"},{"key":"e_1_3_2_2_14_1","volume-title":"Proc. of the 40th Annual ACM Symposium on Theory of Computing (STOC","author":"Samuel","year":"2008","unstructured":"Samuel I. Daitch and Daniel A. Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms . In Proc. of the 40th Annual ACM Symposium on Theory of Computing (STOC 2008 ). 451--460. https:\/\/doi.org\/10. 1145\/1374376.1374441 arXiv:0803.0988 Samuel I. Daitch and Daniel A. Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms. In Proc. of the 40th Annual ACM Symposium on Theory of Computing (STOC 2008). 451--460. https:\/\/doi.org\/10. 1145\/1374376.1374441 arXiv:0803.0988"},{"key":"e_1_3_2_2_15_1","volume-title":"Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020","volume":"168","author":"Doron Dean","year":"2020","unstructured":"Dean Doron , Jack Murtagh , Salil P. Vadhan , and David Zuckerman . 2020 . Spectral Sparsification via Bounded-Independence Sampling . In Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020 ), Vol. 168 . 39:1--39:21. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.39 arXiv:2002.11237 10.4230\/LIPIcs.ICALP.2020.39 Dean Doron, Jack Murtagh, Salil P. Vadhan, and David Zuckerman. 2020. Spectral Sparsification via Bounded-Independence Sampling. In Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Vol. 168. 39:1--39:21. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.39 arXiv:2002.11237"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2503308.2503352"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332443"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_2_19_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 , Denver, CO, USA, February 7--10 , 2022. IEEE, 989--999. https:\/\/doi.org\/10.1109\/ FOCS52979.2021.00099 arXiv:2012.15675 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, Denver, CO, USA, February 7--10, 2022. IEEE, 989--999. https:\/\/doi.org\/10.1109\/ FOCS52979.2021.00099 arXiv:2012.15675"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00071"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.91"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M113277X"},{"key":"e_1_3_2_2_24_1","volume-title":"Proc. of the 19th International Conference on Principles of Distributed Systems (OPODIS 2015","volume":"46","author":"Holzer Stephan","year":"2015","unstructured":"Stephan Holzer and Nathan Pinsker . 2015 . Approximation of Distances and Shortest Paths in the Broadcast Congest Clique . In Proc. of the 19th International Conference on Principles of Distributed Systems (OPODIS 2015 ), Vol. 46 . 6:1--6:16. https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2015.6 arXiv:1412.3445 10.4230\/LIPIcs.OPODIS.2015.6 Stephan Holzer and Nathan Pinsker. 2015. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In Proc. of the 19th International Conference on Principles of Distributed Systems (OPODIS 2015), Vol. 46. 6:1--6:16. https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2015.6 arXiv:1412.3445"},{"key":"e_1_3_2_2_25_1","volume-title":"Johnson and Joram Lindenstrauss","author":"William","year":"1984","unstructured":"William B. Johnson and Joram Lindenstrauss . 1984 . Extensions of Lipschitz mappings into a Hilbert space 26. Contemporary mathematics 26 (1984). William B. Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space 26. Contemporary mathematics 26 (1984)."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559902"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2948062"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.132"},{"key":"e_1_3_2_2_29_1","volume-title":"Path Finding II: An Algorithm for the Minimum Cost Flow Problem. CoRR abs\/1312.6713","author":"Lee Yin Tat","year":"2013","unstructured":"Yin Tat Lee and Aaron Sidford . 2013 . Path Finding II: An Algorithm for the Minimum Cost Flow Problem. CoRR abs\/1312.6713 (2013). arXiv:1312.6713 Yin Tat Lee and Aaron Sidford. 2013. Path Finding II: An Algorithm for the Minimum Cost Flow Problem. CoRR abs\/1312.6713 (2013). arXiv:1312.6713"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_2_31_1","volume-title":"Solving Linear Programs with rank) Linear System Solves. CoRR abs\/1910.08033","author":"Lee Yin Tat","year":"2019","unstructured":"Yin Tat Lee and Aaron Sidford . 2019. Solving Linear Programs with rank) Linear System Solves. CoRR abs\/1910.08033 ( 2019 ). arXiv:1910.08033 Yin Tat Lee and Aaron Sidford. 2019. Solving Linear Programs with rank) Linear System Solves. CoRR abs\/1910.08033 (2019). arXiv:1910.08033"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.22"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441848"},{"key":"e_1_3_2_2_34_1","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann.  Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_3_2_2_35_1","volume-title":"Randomized Algorithms for Matrices and Data. Foundations and Trends\u00ae in Machine Learning 3, 2","author":"Mahoney Michael W.","year":"2011","unstructured":"Michael W. Mahoney . 2011. Randomized Algorithms for Matrices and Data. Foundations and Trends\u00ae in Machine Learning 3, 2 ( 2011 ), 123--224. https:\/\/doi. org\/10.1561\/2200000035 arXiv:1104.5557 Michael W. Mahoney. 2011. Randomized Algorithms for Matrices and Data. Foundations and Trends\u00ae in Machine Learning 3, 2 (2011), 123--224. https:\/\/doi. org\/10.1561\/2200000035 arXiv:1104.5557"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.  David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"#cr-split#-e_1_3_2_2_39_1.1","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM. https: \/\/doi.org\/10.1137\/1.9780898718003 10.1137\/1.9780898718003","DOI":"10.1137\/1.9780898718003"},{"key":"#cr-split#-e_1_3_2_2_39_1.2","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM. https: \/\/doi.org\/10.1137\/1.9780898718003","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13562-0_2"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451108"},{"key":"e_1_3_2_2_45_1","volume-title":"Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends\u00ae in Theoretical Computer Science 10, 1--2","author":"Woodruff David P.","year":"2014","unstructured":"David P. Woodruff . 2014. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends\u00ae in Theoretical Computer Science 10, 1--2 ( 2014 ), 1--157. https:\/\/doi.org\/10.1561\/0400000060 arXiv:1411.4357 10.1561\/0400000060 David P. Woodruff. 2014. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends\u00ae in Theoretical Computer Science 10, 1--2 (2014), 1--157. https:\/\/doi.org\/10.1561\/0400000060 arXiv:1411.4357"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","location":"Salerno Italy","acronym":"PODC '22","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3538436","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538436","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538436"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":44,"alternative-id":["10.1145\/3519270.3538436","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538436","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"}}]}}