{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:31:59Z","timestamp":1753439519784,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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,6,9]]},"DOI":"10.1145\/3519935.3520047","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1080-1092","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel"],"prefix":"10.1145","author":[{"given":"Merav","family":"Parter","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805875.2805976"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89572"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008","author":"Baswana Surender","year":"2008","unstructured":"Surender Baswana and Soumojit Sarkar . 2008 . Fully dynamic algorithm for graph spanners with poly-logarithmic update time . In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008 , San Francisco, California, USA , January 20-22, 2008, Shang-Hua Teng (Ed.). SIAM, 1125\u20131134. Surender Baswana and Soumojit Sarkar. 2008. Fully dynamic algorithm for graph spanners with poly-logarithmic update time. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, Shang-Hua Teng (Ed.). SIAM, 1125\u20131134."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1255378.1255381"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.115"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461784"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.123"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.174"},{"key":"e_1_3_2_1_10_1","volume-title":"Partially Optimal Edge Fault-Tolerant Spanners. CoRR, abs\/2102.11360","author":"Bodwin Greg","year":"2021","unstructured":"Greg Bodwin , Michael Dinitz , and Caleb Robelle . 2021. Partially Optimal Edge Fault-Tolerant Spanners. CoRR, abs\/2102.11360 ( 2021 ), arXiv:2102.11360. arxiv:2102.11360 Greg Bodwin, Michael Dinitz, and Caleb Robelle. 2021. Partially Optimal Edge Fault-Tolerant Spanners. CoRR, abs\/2102.11360 (2021), arXiv:2102.11360. arxiv:2102.11360"},{"key":"e_1_3_2_1_11_1","volume-title":"Fully Dynamic Spanners with Worst-Case Update Time. In 24th Annual European Symposium on Algorithms, ESA 2016","volume":"18","author":"Bodwin Greg","year":"2016","unstructured":"Greg Bodwin and Sebastian Krinninger . 2016 . Fully Dynamic Spanners with Worst-Case Update Time. In 24th Annual European Symposium on Algorithms, ESA 2016 , August 22-24, 2016, Aarhus, Denmark, Piotr Sankowski and Christos D. Zaroliagis (Eds.) (LIPIcs , Vol. 57). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317: 18 . Greg Bodwin and Sebastian Krinninger. 2016. Fully Dynamic Spanners with Worst-Case Update Time. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, Piotr Sankowski and Christos D. Zaroliagis (Eds.) (LIPIcs, Vol. 57). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317:18."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331588"},{"key":"e_1_3_2_1_13_1","volume-title":"31st International Symposium on Distributed Computing, DISC 2017","volume":"16","author":"Censor-Hillel Keren","year":"2017","unstructured":"Keren Censor-Hillel , Merav Parter , and Gregory Schwartzman . 2017 . Derandomizing Local Distributed Algorithms under Bandwidth Restrictions . In 31st International Symposium on Distributed Computing, DISC 2017 , October 16-20, 2017, Vienna, Austria, Andr\u00e9a W. Richa (Ed.) (LIPIcs , Vol. 91). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 11:1\u201311: 16 . Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. 2017. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, Andr\u00e9a W. Richa (Ed.) (LIPIcs, Vol. 91). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 11:1\u201311:16."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/090758039"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222013"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Theory of Computing","author":"Cheriyan Joseph","year":"1991","unstructured":"Joseph Cheriyan and Ramakrishna Thurimella . 1991 . Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract) . In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing , May 5-8, 1991, New Orleans, Louisiana, USA, Cris Koutsougeras and Jeffrey Scott Vitter (Eds.). ACM, 391\u2013401. Joseph Cheriyan and Ramakrishna Thurimella. 1991. Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, Cris Koutsougeras and Jeffrey Scott Vitter (Eds.). ACM, 391\u2013401."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115953.3115997"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316346"},{"key":"e_1_3_2_1_19_1","volume-title":"New Graph Spanners and the Greedy Algorithms. 9th Workshop on Advances in Distributed Graph Algorithms. http:\/\/adga.hiit.fi\/2020\/","author":"Dinitz Michael","year":"2020","unstructured":"Michael Dinitz . 2020 . New Graph Spanners and the Greedy Algorithms. 9th Workshop on Advances in Distributed Graph Algorithms. http:\/\/adga.hiit.fi\/2020\/ Michael Dinitz. 2020. New Graph Spanners and the Greedy Algorithms. 9th Workshop on Advances in Distributed Graph Algorithms. http:\/\/adga.hiit.fi\/2020\/"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993830"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405735"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/050641661"},{"key":"e_1_3_2_1_23_1","unstructured":"Paul Erd\u0151s. 1964. Extremal problems in graph theory. In IN THEORY OF GRAPHS AND ITS APPLICATIONS PROC. SYMPOS. SMOLENICE.  Paul Erd\u0151s. 1964. Extremal problems in graph theory. In IN THEORY OF GRAPHS AND ITS APPLICATIONS PROC. SYMPOS. SMOLENICE."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.113"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.126"},{"key":"e_1_3_2_1_26_1","volume-title":"DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, Yehuda Afek (Ed.) (Lecture Notes in Computer Science","volume":"15","author":"Ghaffari Mohsen","year":"2013","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2013 . Distributed Minimum Cut Approximation. In Distributed Computing - 27th International Symposium , DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, Yehuda Afek (Ed.) (Lecture Notes in Computer Science , Vol. 8205). Springer, 1\u2013 15 . Mohsen Ghaffari and Fabian Kuhn. 2013. Distributed Minimum Cut Approximation. In Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, Yehuda Afek (Ed.) (Lecture Notes in Computer Science, Vol. 8205). Springer, 1\u201315."},{"key":"e_1_3_2_1_27_1","volume-title":"Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In 32nd International Symposium on Distributed Computing, DISC 2018","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2018 . Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In 32nd International Symposium on Distributed Computing, DISC 2018 , New Orleans, LA, USA , October 15-19, 2018, Ulrich Schmid and Josef Widder (Eds.) (LIPIcs, Vol. 121). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 29:1\u201329:17. Mohsen Ghaffari and Fabian Kuhn. 2018. Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, Ulrich Schmid and Josef Widder (Eds.) (LIPIcs, Vol. 121). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 29:1\u201329:17."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090267"},{"key":"e_1_3_2_1_29_1","volume-title":"ACM Symposium on Principles of Distributed Computing, PODC \u201914","author":"Kapralov Michael","year":"2014","unstructured":"Michael Kapralov and David P. Woodruff . 2014. Spanners and sparsifiers in dynamic streams . In ACM Symposium on Principles of Distributed Computing, PODC \u201914 , Paris, France , July 15-18, 2014 , Magn\u00fas M. Halld\u00f3rsson and Shlomi Dolev (Eds.). ACM, 272\u2013281. Michael Kapralov and David P. Woodruff. 2014. Spanners and sparsifiers in dynamic streams. In ACM Symposium on Principles of Distributed Computing, PODC \u201914, Paris, France, July 15-18, 2014, Magn\u00fas M. Halld\u00f3rsson and Shlomi Dolev (Eds.). ACM, 272\u2013281."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794273083"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63492"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276734"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451088"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313872"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2019.30"},{"key":"e_1_3_2_1_37_1","volume-title":"Local Computation Algorithms for Spanners. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019","volume":"21","author":"Parter Merav","year":"2019","unstructured":"Merav Parter , Ronitt Rubinfeld , Ali Vakilian , and Anak Yodpinyanee . 2019 . Local Computation Algorithms for Spanners. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019 , January 10-12, 2019, San Diego, California, USA, Avrim Blum (Ed.) (LIPIcs , Vol. 124). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 58:1\u201358: 21 . Merav Parter, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. 2019. Local Computation Algorithms for Spanners. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, Avrim Blum (Ed.) (LIPIcs, Vol. 124). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 58:1\u201358:21."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2018.40"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_40_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":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224968"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520047","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":45,"alternative-id":["10.1145\/3519935.3520047","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520047","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}