{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:10:48Z","timestamp":1787497848265,"version":"build-2736575974"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,12,8]],"date-time":"2015-12-08T00:00:00Z","timestamp":1449532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation (NSF) CAREER","award":["CCF-1149048"],"award-info":[{"award-number":["CCF-1149048"]}]},{"name":"NSF graduate fellowship"},{"name":"NSF","award":["CCF-1018463"],"award-info":[{"award-number":["CCF-1018463"]}]},{"name":"Microsoft research fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"\n We study algorithms for spectral graph sparsification. The input is a graph\n G<\/jats:italic>\n with\n n<\/jats:italic>\n vertices and\n m<\/jats:italic>\n edges, and the output is a sparse graph\n G\u02dc<\/jats:italic>\n that approximates\n G<\/jats:italic>\n in an algebraic sense. Concretely, for all vectors\n x<\/jats:italic>\n and any \u03f5 > 0, the graph\n G\u02dc<\/jats:italic>\n satisfies (1-\u03f5 )\n \n x\n \n T<\/jats:italic>\n <\/jats:sup>\n L<\/jats:italic>\n \n G<\/jats:italic>\n <\/jats:sub>\n \n x<\/jats:italic>\n <\/jats:sup>\n <\/jats:italic>\n \u2264\n x<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sup>\n L<\/jats:italic>\n G\u02dc<\/jats:italic>\n \n x<\/jats:italic>\n <\/jats:sup>\n \u2264 (1+\u03f5)\n x<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sup>\n L<\/jats:italic>\n \n G<\/jats:italic>\n <\/jats:sub>\n \n x<\/jats:italic>\n <\/jats:sup>\n , where\n \n L\n G<\/jats:sub>\n <\/jats:italic>\n and\n G\u02dc<\/jats:italic>\n are the Laplacians of\n G<\/jats:italic>\n and\n G\u02dc<\/jats:italic>\n respectively.\n <\/jats:p>\n \n The first contribution of this article applies to all existing sparsification algorithms that rely on solving solving linear systems on graph Laplacians. These algorithms are the fastest known to date. Specifically, we show that less precision is required in the solution of the linear systems, leading to speedups by an\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ) factor. We also present faster sparsification algorithms for slightly dense graphs:\n <\/jats:p>\n \n \u2014 An\n O<\/jats:italic>\n (\n m<\/jats:italic>\n log\n n<\/jats:italic>\n ) time algorithm that generates a sparsifier with\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n 3<\/jats:sup>\n n<\/jats:italic>\n \/\u03f5\n 2<\/jats:sup>\n ) edges.\n <\/jats:p>\n \n \u2014 An\n O<\/jats:italic>\n (\n m<\/jats:italic>\n log log\n n<\/jats:italic>\n ) time algorithm for graphs with more than\n n<\/jats:italic>\n log\n 5<\/jats:sup>\n n<\/jats:italic>\n log log\n n<\/jats:italic>\n edges.\n <\/jats:p>\n \n \u2014 An\n O<\/jats:italic>\n (\n m<\/jats:italic>\n ) algorithm for graphs with more than\n n<\/jats:italic>\n log\n 10<\/jats:sup>\n n<\/jats:italic>\n edges.\n <\/jats:p>\n \n \u2014 An\n O<\/jats:italic>\n (\n m<\/jats:italic>\n ) algorithm for unweighted graphs with more than\n n<\/jats:italic>\n log\n 8<\/jats:sup>\n n<\/jats:italic>\n edges.\n <\/jats:p>\n \n These bounds hold up to factors that are in\n O<\/jats:italic>\n (\n poly<\/jats:italic>\n (log log\n n<\/jats:italic>\n )) and are conjectured to be removable.\n <\/jats:p>","DOI":"10.1145\/2743021","type":"journal-article","created":{"date-parts":[[2015,12,10]],"date-time":"2015-12-10T09:22:10Z","timestamp":1449739330000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices"],"prefix":"10.1145","volume":"12","author":[{"given":"Ioannis","family":"Koutis","sequence":"first","affiliation":[{"name":"University of Puerto Rico-Rio Piedras"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Levin","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.07.018"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_2_1_6_1","volume-title":"Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford.","author":"Cohen Michael B.","year":"2014","unstructured":"Michael B. Cohen , Yin Tat Lee , Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. 2014 b. Uniform sampling for matrix approximation. Available at http:\/\/arxiv.org\/abs\/1408.5099 Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. 2014b. Uniform sampling for matrix approximation. Available at http:\/\/arxiv.org\/abs\/1408.5099"},{"key":"e_1_2_1_7_1","unstructured":"Michael B. Cohen Gary L. Miller Jakub W. Pachocki Richard Peng and Shen Chen Xu. 2014c. Stretching stretch. Available at http:\/\/arxiv.org\/abs\/1401.2454 Michael B. Cohen Gary L. Miller Jakub W. Pachocki Richard Peng and Shen Chen Xu. 2014c. Stretching stretch. Available at http:\/\/arxiv.org\/abs\/1401.2454"},{"key":"e_1_2_1_8_1","volume-title":"Random Walks and Electric Networks","author":"Doyle Peter G.","unstructured":"Peter G. Doyle and J. Laurie Snell . 2000. Random Walks and Electric Networks . Mathematical Association of America , Washington, DC . Peter G. Doyle and J. Laurie Snell. 2000. Random Walks and Electric Networks. Mathematical Association of America, Washington, DC."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808753"},{"key":"e_1_2_1_11_1","unstructured":"Eran Halperin and Uri Zwick. 1996. Linear time deterministic algorithm for computing spanners for unweighted graphs. Unpublished manuscript. Eran Halperin and Uri Zwick. 1996. Linear time deterministic algorithm for computing spanners for unweighted graphs. Unpublished manuscript."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998)","author":"Karger David R.","year":"1998","unstructured":"David R. Karger . 1998 . Better random sampling algorithms for flows in undirected graphs . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998) . 490--499. http:\/\/dl.acm.org\/citation.cfm?id=314613.314833 David R. Karger. 1998. Better random sampling algorithms for flows in undirected graphs. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998). 490--499. http:\/\/dl.acm.org\/citation.cfm?id=314613.314833"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9396-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612676"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","author":"Koutis Ioannis","year":"2012","unstructured":"Ioannis Koutis , Alex Levin , and Richard Peng . 2012 . Improved spectral sparsification and numerical algorithms for SDD matrices . In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912) . 266--277. Ioannis Koutis, Alex Levin, and Richard Peng. 2012. Improved spectral sparsification and numerical algorithms for SDD matrices. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912). 266--277."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.22"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_2_1_24_1","volume-title":"Spielman and Jaeoh Woo","author":"Daniel","year":"2009","unstructured":"Daniel A. Spielman and Jaeoh Woo . 2009 . A note on preconditioning by low-stretch spanning trees. arXiv:0903.2815. Daniel A. Spielman and Jaeoh Woo. 2009. A note on preconditioning by low-stretch spanning trees. arXiv:0903.2815."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2743021","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2743021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:07:15Z","timestamp":1750208835000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2743021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,8]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2743021"],"URL":"https:\/\/doi.org\/10.1145\/2743021","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,8]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}