{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:42Z","timestamp":1750220382870,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2344\/19"],"award-info":[{"award-number":["2344\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467926","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"235-246","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Ultra-Sparse Near-Additive Emulators"],"prefix":"10.1145","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaked","family":"Matar","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897555"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105815"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805875.2805976"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384321"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.104"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331633"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195089"},{"key":"e_1_3_2_2_8_1","volume-title":"Symposium on Theory of Computing, STOC 2014","author":"Cohen Michael B.","year":"2014","unstructured":"Michael B. Cohen , Rasmus Kyng , Gary L. Miller , Jakub W. Pachocki , Richard Peng , Anup B. Rao , and Shen Chen Xu . 2014 . Solving SDD linear systems in nearly mlog1\/2n time . In Symposium on Theory of Computing, STOC 2014 , New York, NY, USA, May 31 - June 03, 2014, David B. Shmoys (Ed.). ACM, 343--352. https:\/\/doi.org\/10.1145\/2591796.2591833 Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. 2014. Solving SDD linear systems in nearly mlog1\/2n time. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, David B. Shmoys (Ed.). ACM, 343--352. https:\/\/doi.org\/10.1145\/2591796.2591833"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2006.1639362"},{"key":"e_1_3_2_2_10_1","volume-title":"Exponentially Faster Shortest Paths in the Congested Clique. In PODC '20: ACM Symposium on Principles of Distributed Computing","author":"Dory Michal","year":"2020","unstructured":"Michal Dory and Merav Parter . 2020 . Exponentially Faster Shortest Paths in the Congested Clique. In PODC '20: ACM Symposium on Principles of Distributed Computing , Virtual Event, Italy, August 3--7 , 2020, Yuval Emek and Christian Cachin (Eds.). ACM, 59--68. https:\/\/doi.org\/10.1145\/3382734.3405711 Michal Dory and Merav Parter. 2020. Exponentially Faster Shortest Paths in the Congested Clique. In PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3--7, 2020, Yuval Emek and Christian Cachin (Eds.). ACM, 59--68. https:\/\/doi.org\/10.1145\/3382734.3405711"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.04.002"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.383983"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331635"},{"key":"e_1_3_2_2_14_1","volume-title":"Ultra-Sparse Near-Additive Emulators. CoRR","author":"Elkin Michael","year":"2021","unstructured":"Michael Elkin and Shaked Matar . 2021. Ultra-Sparse Near-Additive Emulators. CoRR ( 2021 ). arXiv:cs.DS\/2106.01036 https:\/\/arxiv.org\/abs\/2106.01036 Michael Elkin and Shaked Matar. 2021. Ultra-Sparse Near-Additive Emulators. CoRR (2021). arXiv:cs.DS\/2106.01036 https:\/\/arxiv.org\/abs\/2106.01036"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.22"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933098"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039728"},{"key":"e_1_3_2_2_18_1","volume-title":"Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR abs\/1704.08468","author":"Elkin Michael","year":"2017","unstructured":"Michael Elkin and Ofer Neiman . 2017. Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR abs\/1704.08468 ( 2017 ). arXiv:1704.08468 http:\/\/arxiv.org\/abs\/1704.08468 Michael Elkin and Ofer Neiman. 2017. Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR abs\/1704.08468 (2017). arXiv:1704.08468 http:\/\/arxiv.org\/abs\/1704.08468"},{"key":"e_1_3_2_2_19_1","volume-title":"A Unified View. Bull. EATCS 130","author":"Elkin Michael","year":"2020","unstructured":"Michael Elkin and Ofer Neiman . 2020. Near-Additive Spanners and Near-Exact Hopsets , A Unified View. Bull. EATCS 130 ( 2020 ). http:\/\/bulletin.eatcs.org\/index. php\/beatcs\/article\/view\/608\/624 Michael Elkin and Ofer Neiman. 2020. Near-Additive Spanners and Near-Exact Hopsets, A Unified View. Bull. EATCS 130 (2020). http:\/\/bulletin.eatcs.org\/index. php\/beatcs\/article\/view\/608\/624"},{"key":"e_1_3_2_2_20_1","volume-title":"Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6--8","author":"Elkin Michael","year":"2001","unstructured":"Michael Elkin and David Peleg . 2001 . (1+epsilon, beta)-spanner constructions for general graphs . In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6--8 , 2001, Heraklion, Crete, Greece. 173--182. https:\/\/doi.org\/10. 1145\/380752.380797 Michael Elkin and David Peleg. 2001. (1+epsilon, beta)-spanner constructions for general graphs. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6--8, 2001, Heraklion, Crete, Greece. 173--182. https:\/\/doi.org\/10. 1145\/380752.380797"},{"key":"e_1_3_2_2_21_1","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015","author":"Elkin Michael","year":"2015","unstructured":"Michael Elkin and Seth Pettie . 2015 . A Linear-Size Logarithmic Stretch PathReporting Distance Oracle for General Graphs . In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 , San Diego, CA, USA, January 4--6 , 2015. 805--821. https:\/\/doi.org\/10.1137\/1.9781611973730.55 Michael Elkin and Seth Pettie. 2015. A Linear-Size Logarithmic Stretch PathReporting Distance Oracle for General Graphs. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4--6, 2015. 805--821. https:\/\/doi.org\/10.1137\/1.9781611973730.55"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011791"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/313852.314099"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897638"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3218657"},{"key":"e_1_3_2_2_26_1","volume-title":"Thorup-Zwick Emulators are Universally Optimal Hopsets. CoRR abs\/1705.00327","author":"Huang Shang-En","year":"2017","unstructured":"Shang-En Huang and Seth Pettie . 2017. Thorup-Zwick Emulators are Universally Optimal Hopsets. CoRR abs\/1705.00327 ( 2017 ). arXiv:1705.00327 http:\/\/arxiv. org\/abs\/1705.00327 Shang-En Huang and Seth Pettie. 2017. Thorup-Zwick Emulators are Universally Optimal Hopsets. CoRR abs\/1705.00327 (2017). arXiv:1705.00327 http:\/\/arxiv. org\/abs\/1705.00327"},{"key":"e_1_3_2_2_27_1","volume-title":"16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018","author":"Huang Shang-En","year":"2018","unstructured":"Shang-En Huang and Seth Pettie . 2018 . Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts . In 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018 , June 18 --20 , 2018, Malm\u00f6, Sweden (LIPIcs), David Eppstein (Ed.), Vol. 101. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 26:1--26:12. https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.26 Shang-En Huang and Seth Pettie. 2018. Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts. In 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018, June 18--20, 2018, Malm\u00f6, Sweden (LIPIcs), David Eppstein (Ed.), Vol. 101. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 26:1--26:12. https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.26"},{"key":"e_1_3_2_2_28_1","volume-title":"Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. CoRR abs\/2011.08806","author":"Jambulapati Arun","year":"2020","unstructured":"Arun Jambulapati and Aaron Sidford . 2020. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. CoRR abs\/2011.08806 ( 2020 ). arXiv:2011.08806 https:\/\/arxiv.org\/abs\/2011.08806 Arun Jambulapati and Aaron Sidford. 2020. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. CoRR abs\/2011.08806 (2020). arXiv:2011.08806 https:\/\/arxiv.org\/abs\/2011.08806"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090267"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.16"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806699"},{"key":"e_1_3_2_2_32_1","volume-title":"25th International Colloquium, SIROCCO 2018","author":"Kuhn Fabian","year":"2018","unstructured":"Fabian Kuhn , Yannic Maus , and Simon Weidner . 2018 . Deterministic Distributed Ruling Sets of Line Graphs. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018 , Ma'ale HaHamisha, Israel, June 18--21 , 2018, Revised Selected Papers. 193--208. https: \/\/doi.org\/10.1007\/978--3-030-01325--7_19 Fabian Kuhn, Yannic Maus, and Simon Weidner. 2018. Deterministic Distributed Ruling Sets of Line Graphs. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18--21, 2018, Revised Selected Papers. 193--208. https: \/\/doi.org\/10.1007\/978--3-030-01325--7_19"},{"key":"e_1_3_2_2_33_1","volume-title":"Near-Optimal Decremental Approximate Multi-Source Shortest Paths. CoRR abs\/2009.08416","author":"Lacki Jakub","year":"2020","unstructured":"Jakub Lacki and Yasamin Nazari . 2020. Near-Optimal Decremental Approximate Multi-Source Shortest Paths. CoRR abs\/2009.08416 ( 2020 ). arXiv:2009.08416 https:\/\/arxiv.org\/abs\/2009.08416 Jakub Lacki and Yasamin Nazari. 2020. Near-Optimal Decremental Approximate Multi-Source Shortest Paths. CoRR abs\/2009.08416 (2020). arXiv:2009.08416 https:\/\/arxiv.org\/abs\/2009.08416"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767398"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484262"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_9"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400786"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644022"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"e_1_3_2_2_41_1","volume-title":"12th Annual European Symposium, Bergen, Norway, September 14--17, 2004, Proceedings. 580--591","author":"Roditty Liam","year":"2004","unstructured":"Liam Roditty and Uri Zwick . 2004 . On Dynamic Shortest Paths Problems. In Algorithms - ESA 2004 , 12th Annual European Symposium, Bergen, Norway, September 14--17, 2004, Proceedings. 580--591 . https:\/\/doi.org\/10.1007\/978--3--540--30140-0_52 Liam Roditty and Uri Zwick. 2004. On Dynamic Shortest Paths Problems. In Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14--17, 2004, Proceedings. 580--591. https:\/\/doi.org\/10.1007\/978--3--540--30140-0_52"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2846458.2846519"},{"key":"e_1_3_2_2_43_1","volume-title":"Nearly Maximum Flows in Nearly Linear Time. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013","author":"Sherman Jonah","year":"2013","unstructured":"Jonah Sherman . 2013 . Nearly Maximum Flows in Nearly Linear Time. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013 , 26- 29 October, 2013, Berkeley, CA, USA. IEEE Computer Society, 263--269. https: \/\/doi.org\/10.1109\/FOCS. 2013.36 Jonah Sherman. 2013. Nearly Maximum Flows in Nearly Linear Time. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26- 29 October, 2013, Berkeley, CA, USA. IEEE Computer Society, 263--269. https: \/\/doi.org\/10.1109\/FOCS.2013.36"},{"key":"e_1_3_2_2_44_1","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"Daniel","year":"2004","unstructured":"Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems . In Proceedings of the 36th Annual ACM Symposium on Theory of Computing , Chicago, IL, USA, June 13--16 , 2004 , L\u00e1szl\u00f3 Babai (Ed.). ACM, 81--90. https:\/\/doi.org\/10.1145\/1007352. 1007372 Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13--16, 2004, L\u00e1szl\u00f3 Babai (Ed.). ACM, 81--90. https:\/\/doi.org\/10.1145\/1007352. 1007372"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109645"}],"event":{"name":"PODC '21: 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":"Virtual Event Italy","acronym":"PODC '21"},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":45,"alternative-id":["10.1145\/3465084.3467926","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467926","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}