{"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":1750220335199,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":28,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538469","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"57-59","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Brief Announcement: (1+\u03b5)-Approximate Shortest Paths in Dynamic Streams."],"prefix":"10.1145","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}]},{"given":"Chhaya","family":"Trehan","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, London, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_2_3_1","volume-title":"Proceedings of the Twenty-First Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010","author":"Ba Khanh Do","year":"2010","unstructured":"Khanh Do Ba , Piotr Indyk , Eric Price , and David P. Woodruff . 2010. Lower Bounds for Sparse Recovery . In Proceedings of the Twenty-First Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010 , Austin, Texas, USA, January 17--19 , 2010 , Moses Charikar (Ed.). SIAM, 1190--1197. https:\/\/doi.org\/10.1137\/1. 9781611973075.95 10.1137\/1 Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff. 2010. Lower Bounds for Sparse Recovery. In Proceedings of the Twenty-First Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17--19, 2010, Moses Charikar (Ed.). SIAM, 1190--1197. https:\/\/doi.org\/10.1137\/1. 9781611973075.95"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.11.001"},{"key":"e_1_3_2_2_5_1","volume-title":"Streaming Complexity of Spanning Tree Computation. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020","volume":"19","author":"Chang Yi-Jun","year":"2020","unstructured":"Yi-Jun Chang , Martin Farach-Colton , Tsan-sheng Hsu, and Meng-Tsung Tsai . 2020 . Streaming Complexity of Spanning Tree Computation. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020 , March 10 --13 , 2020, Montpellier, France (LIPIcs, Vol. 154). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 34:1--34: 19 . https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.34 10.4230\/LIPIcs.STACS.2020.34 Yi-Jun Chang, Martin Farach-Colton, Tsan-sheng Hsu, and Meng-Tsung Tsai. 2020. Streaming Complexity of Spanning Tree Computation. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10--13, 2020, Montpellier, France (LIPIcs, Vol. 154). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 34:1--34:19. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.34"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/050630696"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-013-7131-9"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921666"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055452"},{"key":"e_1_3_2_2_10_1","article-title":"Efficient Algorithms for Constructing Very Sparse Spanners and Emulators","volume":"15","author":"Elkin Michael","year":"2018","unstructured":"Michael Elkin and Ofer Neiman . 2018 . Efficient Algorithms for Constructing Very Sparse Spanners and Emulators . ACM Trans. Algorithms 15 , 1, Article 4 (Nov. 2018), 29 pages. https:\/\/doi.org\/10.1145\/3274651 10.1145\/3274651 Michael Elkin and Ofer Neiman. 2018. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Trans. Algorithms 15, 1, Article 4 (Nov. 2018), 29 pages. https:\/\/doi.org\/10.1145\/3274651","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1166791"},{"key":"e_1_3_2_2_12_1","volume-title":"Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication. CoRR abs\/2004.07572","author":"Elkin Michael","year":"2020","unstructured":"Michael Elkin and Ofer Neiman . 2020. Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication. CoRR abs\/2004.07572 ( 2020 ). arXiv:2004.07572 https:\/\/arxiv.org\/abs\/2004.07572 Michael Elkin and Ofer Neiman. 2020. Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication. CoRR abs\/2004.07572 (2020). arXiv:2004.07572 https:\/\/arxiv.org\/abs\/2004.07572"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380797"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627854"},{"key":"e_1_3_2_2_15_1","volume-title":"Approximate Shortest Paths in Dynamic Streams. CoRR abs\/2107.13309","author":"Elkin Michael","year":"2021","unstructured":"Michael Elkin and Chhaya Trehan . 2021. Approximate Shortest Paths in Dynamic Streams. CoRR abs\/2107.13309 ( 2021 ). arXiv:2107.13309 https: \/\/arxiv.org\/abs\/2107.13309 Michael Elkin and Chhaya Trehan. 2021. Approximate Shortest Paths in Dynamic Streams. CoRR abs\/2107.13309 (2021). arXiv:2107.13309 https: \/\/arxiv.org\/abs\/2107.13309"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0147-2"},{"volume-title":"On Graph Problems in a Semi-streaming Model","author":"Feigenbaum Joan","key":"e_1_3_2_2_17_1","unstructured":"Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , and Jian Zhang . 2004. On Graph Problems in a Semi-streaming Model . In Automata, Languages and Programming, Josep D\u00edaz, Juhani Karhum\u00e4ki, Arto Lepist\u00f6, and Donald Sannella (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 531--543. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2004. On Graph Problems in a Semi-streaming Model. In Automata, Languages and Programming, Josep D\u00edaz, Juhani Karhum\u00e4ki, Arto Lepist\u00f6, and Donald Sannella (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 531--543."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_3_2_2_19_1","volume-title":"Graph Spanners in the Message-Passing Model. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020","author":"Fernandez Manuel","year":"2020","unstructured":"Manuel Fernandez , David P. Woodruff , and Taisuke Yasuda . 2020 . Graph Spanners in the Message-Passing Model. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 , January 12 --14 , 2020, Seattle, Washington, USA (LIPIcs, Vol. 151). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 77:1--77:18. https: \/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.77 10.4230\/LIPIcs.ITCS.2020.77 Manuel Fernandez, David P.Woodruff, and Taisuke Yasuda. 2020. Graph Spanners in the Message-Passing Model. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12--14, 2020, Seattle, Washington, USA (LIPIcs, Vol. 151). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 77:1--77:18. https: \/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.77"},{"key":"e_1_3_2_2_20_1","volume-title":"Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model. 1894--","author":"Filtser Arnold","year":"1913","unstructured":"Arnold Filtser , Michael Kapralov , and Navid Nouri . 2021. Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model. 1894-- 1913 . Arnold Filtser, Michael Kapralov, and Navid Nouri. 2021. Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model. 1894-- 1913."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.031"},{"key":"e_1_3_2_2_22_1","volume-title":"Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR abs\/1509.06464","author":"Gibb David","year":"2015","unstructured":"David Gibb , Bruce M. Kapron , Valerie King , and Nolan Thorn . 2015. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR abs\/1509.06464 ( 2015 ). arXiv:1509.06464 http:\/\/arxiv.org\/abs\/1509.06464 David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. 2015. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR abs\/1509.06464 (2015). arXiv:1509.06464 http:\/\/arxiv.org\/abs\/1509.06464"},{"key":"e_1_3_2_2_23_1","volume-title":"On the Power of Adaptivity in Sparse Recovery. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011","author":"Indyk Piotr","year":"2011","unstructured":"Piotr Indyk , Eric Price , and David P. Woodruff . 2011 . On the Power of Adaptivity in Sparse Recovery. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 , Palm Springs, CA, USA, October 22--25 , 2011 , Rafail Ostrovsky (Ed.). IEEE Computer Society, 285--294. https:\/\/doi.org\/10.1109\/FOCS.2011.83 10.1109\/FOCS.2011.83 Piotr Indyk, Eric Price, and David P. Woodruff. 2011. On the Power of Adaptivity in Sparse Recovery. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22--25, 2011, Rafail Ostrovsky (Ed.). IEEE Computer Society, 285--294. https:\/\/doi.org\/10.1109\/FOCS.2011.83"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611497"},{"key":"e_1_3_2_2_25_1","volume-title":"Construction and impromptu repair of an MST in a distributed network with o(m) communication. CoRR abs\/1502.03320","author":"King Valerie","year":"2015","unstructured":"Valerie King , Shay Kutten , and Mikkel Thorup . 2015. Construction and impromptu repair of an MST in a distributed network with o(m) communication. CoRR abs\/1502.03320 ( 2015 ). arXiv:1502.03320 http:\/\/arxiv.org\/abs\/1502.03320 Valerie King, Shay Kutten, and Mikkel Thorup. 2015. Construction and impromptu repair of an MST in a distributed network with o(m) communication. CoRR abs\/1502.03320 (2015). arXiv:1502.03320 http:\/\/arxiv.org\/abs\/1502.03320"},{"key":"e_1_3_2_2_26_1","volume-title":"Proceedings of a DIMACS Workshop","volume":"10","author":"Lazebnik Felix","year":"1992","unstructured":"Felix Lazebnik and Vasiliy A. Ustimenko . 1992. Some Algebraic Constructions of Dense Graphs of Large Girth and of Large Size. In Expanding Graphs , Proceedings of a DIMACS Workshop , Princeton, New Jersey, USA, May 11--14 , 1992 , Vol. 10 . 75--93. https:\/\/doi.org\/10.1090\/dimacs\/010\/07 10.1090\/dimacs Felix Lazebnik and Vasiliy A. Ustimenko. 1992. Some Algebraic Constructions of Dense Graphs of Large Girth and of Large Size. In Expanding Graphs, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, May 11--14, 1992, Vol. 10. 75--93. https:\/\/doi.org\/10.1090\/dimacs\/010\/07"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_2_28_1","volume-title":"Proceedings of the Twenty-First Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010","author":"Monemizadeh Morteza","year":"2010","unstructured":"Morteza Monemizadeh and David P. Woodruff . 2010. 1-Pass Relative-Error Lp-Sampling with Applications . In Proceedings of the Twenty-First Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010 , Austin, Texas, USA, January 17--19 , 2010 , Moses Charikar (Ed.). SIAM, 1143--1160. https:\/\/doi.org\/10.1137\/1. 9781611973075.92 10.1137\/1 Morteza Monemizadeh and David P. Woodruff. 2010. 1-Pass Relative-Error Lp-Sampling with Applications. In Proceedings of the Twenty-First Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17--19, 2010, Moses Charikar (Ed.). SIAM, 1143--1160. https:\/\/doi.org\/10.1137\/1. 9781611973075.92"}],"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.3538469","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538469","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.3538469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":28,"alternative-id":["10.1145\/3519270.3538469","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538469","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"}}]}}