{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T18:43:15Z","timestamp":1783536195601,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":22,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T00:00:00Z","timestamp":1783296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,6]]},"DOI":"10.1145\/3816782.3819201","type":"proceedings-article","created":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:28:33Z","timestamp":1783531713000},"page":"75-86","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Spectral Graph Sparsification via Low Diameter Decompositions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-6901-7479","authenticated-orcid":false,"given":"Yves","family":"Baumann","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-6046-281X","authenticated-orcid":false,"given":"Gernot","family":"Z\u00f6cklein","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Noah Amsel Yves Baumann Paul Beckman Peter B\u00fcrgisser Chris Cama\u00f1o Tyler Chen Edmond Chow Anil Damle Michal Derezinski Mark Embree Ethan N. Epperly Robert Falgout Mark Fornace Anne Greenbaum Chen Greif Diana Halikias Zhen Huang Elias Jarlebring Yiannis Koutis Daniel Kressner Rasmus Kyng J\u00f6rg Liesen Jackie Lok Raphael A. Meyer Yuji Nakatsukasa Kate Pearce Richard Peng David Persson Eliza Rebrova Ryan Schneider Rikhav Shah Edgar Solomonik Nikhil Srivastava Alex Townsend Robert J. Webber and Jess Williams. 2026. Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop. arXiv:2602.05394 [math.NA] https:\/\/arxiv.org\/abs\/2602.05394"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659987"},{"key":"e_1_3_2_1_4_1","volume-title":"Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 293\u2013304","author":"Dhulipala Laxman","year":"2018","unstructured":"Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2018. Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 293\u2013304."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3398682.3399168"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316381"},{"key":"e_1_3_2_1_7_1","volume-title":"Spielman","author":"Gao Yuan","year":"2023","unstructured":"Yuan Gao, Rasmus Kyng, and Daniel A. Spielman. 2023. Robust and Practical Solution of Laplacian Equations by Approximate Elimination. arXiv:2303.00709 [math.NA] https:\/\/arxiv.org\/abs\/2303.00709"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090267"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Ioannis Koutis. 2014. Simple parallel and distributed algorithms for spectral graph sparsification. arXiv:1402.3851 [cs.DS] https:\/\/arxiv.org\/abs\/1402.3851","DOI":"10.1145\/2612669.2612676"},{"key":"e_1_3_2_1_10_1","unstructured":"Ioannis Koutis Alex Levin and Richard Peng. 2013. Faster spectral sparsification and numerical algorithms for SDD matrices. arXiv:1209.5821 [cs.DS] https:\/\/arxiv.org\/abs\/1209.5821"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743021"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS63196.2025.00113"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039818"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian Elimination for Laplacians: Fast Sparse and Simple. arXiv:1605.02353 [cs.DS] https:\/\/arxiv.org\/abs\/1605.02353","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591101"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_21_1","volume-title":"Spielman and Shang-Hua Teng","author":"Daniel","year":"2008","unstructured":"Daniel A. Spielman and Shang-Hua Teng. 2008. Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems. arXiv:cs\/0310051 [cs.DS] https:\/\/arxiv.org\/abs\/cs\/0310051"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"}],"event":{"name":"SPAA '26: 38th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Royal Holloway, University of London London United Kingdom","acronym":"SPAA '26","sponsor":["SIGARCH ACM Special Interest Group on Computer Architecture","SIGACT ACM Special Interest Group on Algorithms and Computation Theory","EATCS"]},"container-title":["Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3816782.3819201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:28:44Z","timestamp":1783531724000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3816782.3819201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,6]]},"references-count":22,"alternative-id":["10.1145\/3816782.3819201","10.1145\/3816782"],"URL":"https:\/\/doi.org\/10.1145\/3816782.3819201","relation":{},"subject":[],"published":{"date-parts":[[2026,7,6]]},"assertion":[{"value":"2026-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}