{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:47Z","timestamp":1750220327000,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"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"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1814603, CCF-1910588, CCF-1750808"],"award-info":[{"award-number":["CCF-1814603, CCF-1910588, CCF-1750808"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["853109, 949272"],"award-info":[{"award-number":["853109, 949272"]}],"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,11]]},"DOI":"10.1145\/3490148.3538565","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates"],"prefix":"10.1145","author":[{"given":"Marcel","family":"Bezdrighin","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Michael","family":"Elkin","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beersheba, Israel"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Christoph","family":"Grunau","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[{"name":"ETH Zurich & Carnegie Mellon University, Zurich, Switzerland"}]},{"given":"Saeed","family":"Ilchi","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"V\u00e1clav","family":"Rozho\u0148","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088511"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2020.100253"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805875.2805976"},{"key":"e_1_3_2_1_5_1","volume-title":"Near- Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers. In 34th Annual Symposium on Foundations of Computer Science","author":"Awerbuch Baruch","year":"1993","unstructured":"Baruch Awerbuch , Bonnie Berger , Lenore Cowen , and David Peleg . 1993 . Near- Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers. In 34th Annual Symposium on Foundations of Computer Science , Palo Alto, California, USA, 3- -5 November 1993. 638--647. https:\/\/doi.org\/10.1109\/SFCS.1993. 366823 10.1109\/SFCS.1993 Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. 1993. Near- Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3--5 November 1993. 638--647. https:\/\/doi.org\/10.1109\/SFCS.1993. 366823"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.07.005"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868242"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Marcel Bezdrighin Michael Elkin Mohsen Ghaffari Christoph Grunau Bernhard Haeupler Saeed Ilchi and V\u00e1clav Rozho\u0148. 2022. Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. https:\/\/doi.org\/10. 48550\/ARXIV.2204.14086  Marcel Bezdrighin Michael Elkin Mohsen Ghaffari Christoph Grunau Bernhard Haeupler Saeed Ilchi and V\u00e1clav Rozho\u0148. 2022. Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. https:\/\/doi.org\/10. 48550\/ARXIV.2204.14086","DOI":"10.1145\/3490148.3538565"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9444-5"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-019-00353-3"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0306-2"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467933"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.36"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366822"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316346"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"Samuel","year":"2008","unstructured":"Samuel I. Daitch and Daniel A. Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms . In Proceedings of the 40th Annual ACM Symposium on Theory of Computing , Victoria, British Columbia, Canada, May 17--20 , 2008 , Cynthia Dwork (Ed.). ACM, 451--460. https:\/\/doi.org\/10.1145\/ 1374376.1374441 Samuel I. Daitch and Daniel A. Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17--20, 2008, Cynthia Dwork (Ed.). ACM, 451--460. https:\/\/doi.org\/10.1145\/ 1374376.1374441"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400788"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04355-0_20"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9190-x"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331626"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212760"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331635"},{"key":"e_1_3_2_1_28_1","first-page":"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 Transactions on Algorithms (TALG) 15 , 1 (2018), 1 -- 29 . Michael Elkin and Ofer Neiman. 2018. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG) 15, 1 (2018), 1--29.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the Symposium on Theory of Graphs and its Applications. 2936","author":"Erd's Paul","year":"1963","unstructured":"Paul Erd's . 1963 . Extremal problems in graph theory . In Proceedings of the Symposium on Theory of Graphs and its Applications. 2936 . Paul Erd's. 1963. Extremal problems in graph theory. In Proceedings of the Symposium on Theory of Graphs and its Applications. 2936."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_1_33_1","volume-title":"32nd International Symposium on Distributed Computing (DISC","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). 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)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a017"},{"key":"e_1_3_2_1_35_1","volume-title":"Improved Deterministic Distributed Construction of Spanners. In 31 International Symposium on Distributed Computing.","author":"Grossman Ofer","year":"2017","unstructured":"Ofer Grossman and Merav Parter . 2017 . Improved Deterministic Distributed Construction of Spanners. In 31 International Symposium on Distributed Computing. Ofer Grossman and Merav Parter. 2017. Improved Deterministic Distributed Construction of Spanners. In 31 International Symposium on Distributed Computing."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.383"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0929"},{"key":"e_1_3_2_1_38_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"Lenzen Christoph","year":"2018","unstructured":"Christoph Lenzen and Reut Levi . 2018 . A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9 --13 , 2018, Prague, Czech Republic. 87:1--87:14. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.87 10.4230\/LIPIcs.ICALP.2018.87 Christoph Lenzen and Reut Levi. 2018. A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9--13, 2018, Prague, Czech Republic. 87:1--87:14. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.87"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384268"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Gary L. Miller Richard Peng Adrian Vladu and Shen Chen Xu. 2015. Improved Parallel Algorithms for Spanners and Hopsets. arXiv:1309.3545 [cs.DS]  Gary L. Miller Richard Peng Adrian Vladu and Shen Chen Xu. 2015. Improved Parallel Algorithms for Spanners and Hopsets. arXiv:1309.3545 [cs.DS]","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_1_41_1","volume-title":"Small Cuts and Connectivity Certificates: A Fault Tolerant Approach. In 33rd International Symposium on Distributed Computing.","author":"Parter Merav","year":"2019","unstructured":"Merav Parter . 2019 . Small Cuts and Connectivity Certificates: A Fault Tolerant Approach. In 33rd International Symposium on Distributed Computing. Merav Parter. 2019. Small Cuts and Connectivity Certificates: A Fault Tolerant Approach. In 33rd International Symposium on Distributed Computing."},{"key":"e_1_3_2_1_42_1","volume-title":"Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing, DISC 2018","author":"Parter Merav","year":"2018","unstructured":"Merav Parter and Eylon Yogev . 2018 . Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing, DISC 2018 , New Orleans, LA, USA, October 15--19 , 2018. 40:1--40:18. https:\/\/doi.org\/10.4230\/ LIPIcs.DISC.2018.40 Merav Parter and Eylon Yogev. 2018. Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15--19, 2018. 40:1--40:18. https:\/\/doi.org\/10.4230\/ LIPIcs.DISC.2018.40"},{"key":"e_1_3_2_1_43_1","volume-title":"Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing. 3.","author":"Parter Merav","year":"2018","unstructured":"Merav Parter and Eylon Yogev . 2018 . Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing. 3. Merav Parter and Eylon Yogev. 2018. Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing. 3."},{"key":"e_1_3_2_1_44_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_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch130"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644022"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"e_1_3_2_1_49_1","volume-title":"Department of Computer Science 530","author":"Shankar Ram L","year":"2011","unstructured":"L Shankar Ram and Elias Vicari . 2011. Distributed small connected spanning subgraph: Breaking the diameter bound. Technical report\/Swiss Federal Institute of Technology Zurich , Department of Computer Science 530 ( 2011 ). L Shankar Ram and Elias Vicari. 2011. Distributed small connected spanning subgraph: Breaking the diameter bound. Technical report\/Swiss Federal Institute of Technology Zurich, Department of Computer Science 530 (2011)."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109645"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0832"}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Philadelphia PA USA","acronym":"SPAA '22"},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538565","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538565","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538565","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:08Z","timestamp":1750191128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":55,"alternative-id":["10.1145\/3490148.3538565","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538565","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}