{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T18:31:28Z","timestamp":1772303488523,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"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":["Commun. ACM"],"published-print":{"date-parts":[[2013,8]]},"abstract":"<jats:p>Graph sparsification is the approximation of an arbitrary graph by a sparse graph.<\/jats:p>\n          <jats:p>We explain what it means for one graph to be a spectral approximation of another and review the development of algorithms for spectral sparsification. In addition to being an interesting concept, spectral sparsification has been an important tool in the design of nearly linear-time algorithms for solving systems of linear equations in symmetric, diagonally dominant matrices. The fast solution of these linear systems has already led to breakthrough results in combinatorial optimization, including a faster algorithm for finding approximate maximum flows and minimum cuts in an undirected network.<\/jats:p>","DOI":"10.1145\/2492007.2492029","type":"journal-article","created":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T19:12:41Z","timestamp":1374779561000},"page":"87-94","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":124,"title":["Spectral sparsification of graphs"],"prefix":"10.1145","volume":"56","author":[{"given":"Joshua","family":"Batson","sequence":"first","affiliation":[{"name":"Mathematics, MIT"}]},{"given":"Daniel A.","family":"Spielman","sequence":"additional","affiliation":[{"name":"Yale University"}]},{"given":"Nikhil","family":"Srivastava","sequence":"additional","affiliation":[{"name":"Microsoft Research, Bangalore"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[{"name":"Computer Science, USC"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Using petal-decompositions to build a low stretch spanning tree. In","author":"Abraham I.","year":"2012","unstructured":"Abraham , I. , Neiman , O. Using petal-decompositions to build a low stretch spanning tree. In ( 2012 ). Abraham, I., Neiman, O. Using petal-decompositions to build a low stretch spanning tree. In (2012)."},{"key":"e_1_2_1_2_1","volume-title":"Fast computation of low-rank matrix approximations., 2","author":"Achlioptas D.","year":"2007","unstructured":"Achlioptas , D. , Mcsherry , F. Fast computation of low-rank matrix approximations., 2 ( 2007 ), 9. Achlioptas, D., Mcsherry, F. Fast computation of low-rank matrix approximations., 2 (2007), 9."},{"key":"e_1_2_1_3_1","volume-title":"isoperimetric inequalities for graphs, and superconcentrators., 1","author":"Alon N.","year":"1985","unstructured":"Alon , N. , Milman , V.D. \u03bb1 , isoperimetric inequalities for graphs, and superconcentrators., 1 ( 1985 ), 73--88. Alon, N., Milman, V.D. \u03bb1, isoperimetric inequalities for graphs, and superconcentrators., 1 (1985), 73--88."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805875.2805976"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536449"},{"key":"e_1_2_1_7_1","volume-title":"Twice-Ramanujan sparsifiers. 6","author":"Batson J.D.","year":"2012","unstructured":"Batson , J.D. , Spielman , D.A. , Srivastava , N. Twice-Ramanujan sparsifiers. 6 ( 2012 ), 1704--1721. Batson, J.D., Spielman, D.A., Srivastava, N. Twice-Ramanujan sparsifiers. 6 (2012), 1704--1721."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_2_1_9_1","volume-title":"The isoperimetric number of random regular graphs., 3 (May","author":"Bollob\u00e1s B.","year":"1988","unstructured":"Bollob\u00e1s , B. The isoperimetric number of random regular graphs., 3 (May 1988 ), 241--244. Bollob\u00e1s, B. The isoperimetric number of random regular graphs., 3 (May 1988), 241--244."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73062"},{"key":"e_1_2_1_11_1","volume-title":"A lower bound for smallest eigenvalue of Laplacian. In","author":"Cheeger J.","year":"1970","unstructured":"Cheeger , J. A lower bound for smallest eigenvalue of Laplacian. In ( 1970 ), Princeton University Press , 195--199. Cheeger, J. A lower bound for smallest eigenvalue of Laplacian. In (1970), Princeton University Press, 195--199."},{"key":"e_1_2_1_12_1","volume-title":"Rumour spreading and graph conductance. In","author":"Chierichetti F.","year":"2010","unstructured":"Chierichetti , F. , Lattanzi , S. , Panconesi , A. Rumour spreading and graph conductance. In ( 2010 ), 1657--1663. Chierichetti, F., Lattanzi, S., Panconesi, A. Rumour spreading and graph conductance. In (2010), 1657--1663."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_2_1_14_1","volume-title":"Spectral graph theory. CBMS Regional Conference Series in Mathematics","author":"Chung F.R.K.","year":"1997","unstructured":"Chung , F.R.K. Spectral graph theory. CBMS Regional Conference Series in Mathematics , American Mathematical Society , 1997 . Chung, F.R.K. Spectral graph theory. CBMS Regional Conference Series in Mathematics, American Mathematical Society, 1997."},{"key":"e_1_2_1_15_1","unstructured":"de Carli Silva M.K. Harvey N.J.A. Sato C.M. Sparse sums of positive semidefinite matrices. (2011) abs\/1107.0088.  de Carli Silva M.K. Harvey N.J.A. Sato C.M. Sparse sums of positive semidefinite matrices. (2011) abs\/1107.0088."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993646"},{"key":"e_1_2_1_17_1","volume-title":"A Proof of Alon's Second Eigenvalue Conjecture and Related Problems. Number 910 in Memoirs of the American Mathematical Society","author":"Friedman J.","year":"2008","unstructured":"Friedman , J. A Proof of Alon's Second Eigenvalue Conjecture and Related Problems. Number 910 in Memoirs of the American Mathematical Society . American Mathematical Society , 2008 . Friedman, J. A Proof of Alon's Second Eigenvalue Conjecture and Related Problems. Number 910 in Memoirs of the American Mathematical Society. American Mathematical Society, 2008."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_2_1_19_1","volume-title":"Matrix Computations","author":"Golub G.H.","year":"1989","unstructured":"Golub , G.H. , Van Loan , C.F. Matrix Computations , 2 nd edn, Johns Hopkins University Press , 1989 . Golub, G.H., Van Loan, C.F. Matrix Computations, 2nd edn, Johns Hopkins University Press, 1989.","edition":"2"},{"key":"e_1_2_1_20_1","volume-title":"Expanders via random spanning trees. In","author":"Goyal N.","year":"2009","unstructured":"Goyal , N. , Rademacher , L. , Vempala , S. Expanders via random spanning trees. In ( 2009 ), 576--585. Goyal, N., Rademacher, L., Vempala, S. Expanders via random spanning trees. In (2009), 576--585."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090267"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806699"},{"key":"e_1_2_1_23_1","volume-title":"Improved spectral sparsification and numerical algorithms for SDD matrices. In","author":"Koutis I.","year":"2012","unstructured":"Koutis , I. , Levin , A. , Peng , R. Improved spectral sparsification and numerical algorithms for SDD matrices. In ( 2012 ), 266--277. Koutis, I., Levin, A., Peng, R. Improved spectral sparsification and numerical algorithms for SDD matrices. In (2012), 266--277."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Leiserson C. Fat-trees: universal networks for hardware-efficient supercomputing. 10 (0ctober1985) 892--901.   Leiserson C. Fat-trees: universal networks for hardware-efficient supercomputing. 10 (0ctober1985) 892--901.","DOI":"10.1109\/TC.1985.6312192"},{"key":"e_1_2_1_26_1","volume-title":"Ramanujan graphs., 3","author":"Lubotzky A.","year":"1988","unstructured":"Lubotzky , A. , Phillips , R. , Sarnak , P. Ramanujan graphs., 3 ( 1988 ), 261--277. Lubotzky, A., Phillips, R., Sarnak, P. Ramanujan graphs., 3 (1988), 261--277."},{"key":"e_1_2_1_27_1","volume-title":"Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators., 1 (July","author":"Margulis G.A.","year":"1988","unstructured":"Margulis , G.A. Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators., 1 (July 1988 ), 39--46. Margulis, G.A. Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators., 1 (July 1988), 39--46."},{"key":"e_1_2_1_28_1","unstructured":"Naor A. Sparse quadratic forms and their geometric applications. (2011) 1033.  Naor A. Sparse quadratic forms and their geometric applications. (2011) 1033."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_2_1_30_1","volume-title":"Random vectors in the isotropic position., 1","author":"Rudelson M.","year":"1999","unstructured":"Rudelson , M. Random vectors in the isotropic position., 1 ( 1999 ), 60--72. Rudelson, M. Random vectors in the isotropic position., 1 (1999), 60--72."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_2_1_33_1","unstructured":"Spielman D.A. Teng S.H. Nearly-linear time algorithms for preconditioning and solving symmetric diagonally dominant linear systems. (2008) abs\/cs\/0607105.  Spielman D.A. Teng S.H. Nearly-linear time algorithms for preconditioning and solving symmetric diagonally dominant linear systems. (2008) abs\/cs\/0607105."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_2_1_35_1","volume-title":"Learning from labeled and unlabeled data on a directed graph. In","author":"Zhou D.","year":"2005","unstructured":"Zhou , D. , Huang , J. , Scholkopf , B. Learning from labeled and unlabeled data on a directed graph. In ( 2005 ), 1041--1048. Zhou, D., Huang, J., Scholkopf, B. Learning from labeled and unlabeled data on a directed graph. In (2005), 1041--1048."},{"key":"e_1_2_1_36_1","volume-title":"Semi-supervised learning using Gaussian fields and harmonic functions. In","author":"Zhu X.","year":"2003","unstructured":"Zhu , X. , Ghahramani , Z. , Lafferty , J.D. Semi-supervised learning using Gaussian fields and harmonic functions. In ( 2003 ). Zhu, X., Ghahramani, Z., Lafferty, J.D. Semi-supervised learning using Gaussian fields and harmonic functions. In (2003)."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2492007.2492029","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2492007.2492029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:01Z","timestamp":1750235941000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2492007.2492029"}},"subtitle":["theory and algorithms"],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":36,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1145\/2492007.2492029"],"URL":"https:\/\/doi.org\/10.1145\/2492007.2492029","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]},"assertion":[{"value":"2013-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}