{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:06:12Z","timestamp":1775282772957,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"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":[[2013,6]]},"DOI":"10.1145\/2488608.2488724","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:41Z","timestamp":1369758941000},"page":"911-920","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":112,"title":["A simple, combinatorial algorithm for solving SDD systems in nearly-linear time"],"prefix":"10.1145","author":[{"given":"Jonathan A.","family":"Kelner","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Lorenzo","family":"Orecchia","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Zeyuan Allen","family":"Zhu","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Nearly tight low stretch spanning trees. CoRR, abs\/0808.2017","author":"Abraham I.","year":"2008","unstructured":"I. Abraham , Y. Bartal , and O. Neiman . Nearly tight low stretch spanning trees. CoRR, abs\/0808.2017 , 2008 . I. Abraham, Y. Bartal, and O. Neiman. Nearly tight low stretch spanning trees. CoRR, abs\/0808.2017, 2008."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384019"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"Bollobas B.","year":"1998","unstructured":"B. Bollobas . Modern Graph Theory . Springer , 1998 . B. Bollobas. Modern Graph Theory. Springer, 1998."},{"key":"e_1_3_2_1_8_1","volume-title":"Maximum-weight-basis preconditioners. Numerical linear algebra with applications, 11(8--9):695--721","author":"Boman E.","year":"2004","unstructured":"E. Boman , D. Chen , B. Hendrickson , and S. Toledo . Maximum-weight-basis preconditioners. Numerical linear algebra with applications, 11(8--9):695--721 , 2004 . E. Boman, D. Chen, B. Hendrickson, and S. Toledo. Maximum-weight-basis preconditioners. Numerical linear algebra with applications, 11(8--9):695--721, 2004."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/040611781"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801390637"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/347185"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060665"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2077655"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645605.663051"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-723-7","volume-title":"Fundamentals of Computerized Tomography: Image Reconstruction from Projections","author":"Herman G. T.","year":"2009","unstructured":"G. T. Herman . Fundamentals of Computerized Tomography: Image Reconstruction from Projections . Springer Publishing Company, Inc orporated, 2nd edition, 2009 . G. T. Herman. Fundamentals of Computerized Tomography: Image Reconstruction from Projections. Springer Publishing Company, Incorporated, 2nd edition, 2009."},{"key":"e_1_3_2_1_20_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-642-21260-4_14","volume-title":"Bioinformatics Research and Applications","author":"Hodgkinson L.","year":"2011","unstructured":"L. Hodgkinson and R. Karp . Algorithms to detect multiprotein modularity conserved during evolution . In J. Chen, J. Wang, and A. Zelikovsky, editors, Bioinformatics Research and Applications , volume 6674 of Lecture Notes in Computer Science , pages 111 -- 122 . Springer Berlin \/ Heidelberg , 2011 . L. Hodgkinson and R. Karp. Algorithms to detect multiprotein modularity conserved during evolution. In J. Chen, J. Wang, and A. Zelikovsky, editors, Bioinformatics Research and Applications, volume 6674 of Lecture Notes in Computer Science, pages 111--122. Springer Berlin \/ Heidelberg, 2011."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1869.70.185"},{"key":"e_1_3_2_1_22_1","volume-title":"Angenaherte aufl\u00f6sung von systemen linearer gleichungen. Bull. Internat. Acad. Polon.Sci. Lettres A, page 335--357","author":"Kaczmarz S.","year":"1937","unstructured":"S. Kaczmarz . Angenaherte aufl\u00f6sung von systemen linearer gleichungen. Bull. Internat. Acad. Polon.Sci. Lettres A, page 335--357 , 1937 . S. Kaczmarz. Angenaherte aufl\u00f6sung von systemen linearer gleichungen. Bull. Internat. Acad. Polon.Sci. Lettres A, page 335--357, 1937."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.013"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748019"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213979"},{"key":"e_1_3_2_1_26_1","volume-title":"A simple, combinatorial algorithm for solving sdd systems in nearly-linear time. CoRR, abs\/1301.6628","author":"Kelner J. A.","year":"2013","unstructured":"J. A. Kelner , L. Orecchia , A. Sidford , and Z. A. Zhu . A simple, combinatorial algorithm for solving sdd systems in nearly-linear time. CoRR, abs\/1301.6628 , 2013 . J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu. A simple, combinatorial algorithm for solving sdd systems in nearly-linear time. CoRR, abs\/1301.6628, 2013."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2011.05.013"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp203"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/500773"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214080"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.66"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_5"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_39_1","volume-title":"A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR, abs\/0809.3232","author":"Spielman D. A.","year":"2008","unstructured":"D. A. Spielman and S.-H. Teng . A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR, abs\/0809.3232 , 2008 . D. A. Spielman and S.-H. Teng. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR, abs\/0809.3232, 2008."},{"key":"e_1_3_2_1_40_1","volume-title":"Spectral sparsification of graphs. CoRR, abs\/0808.4134","author":"Spielman D. A.","year":"2008","unstructured":"D. A. Spielman and S.-H. Teng . Spectral sparsification of graphs. CoRR, abs\/0808.4134 , 2008 . D. A. Spielman and S.-H. Teng. Spectral sparsification of graphs. CoRR, abs\/0808.4134, 2008."},{"key":"e_1_3_2_1_41_1","volume-title":"Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105v5","author":"Spielman D. A.","year":"2012","unstructured":"D. A. Spielman and S.-H. Teng . Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105v5 , 2012 . D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105v5, 2012."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13562-0_2"},{"key":"e_1_3_2_1_45_1","volume-title":"Unpublished manuscript UIUC","author":"Vaidya P. M.","year":"1990","unstructured":"P. M. Vaidya . Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC 1990 . A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991, Minneapolis ., 1990. P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC 1990. A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991, Minneapolis., 1990."},{"key":"e_1_3_2_1_46_1","unstructured":"N. Vishnoi. Lx=b. Monograph available at http:\/\/research.microsoft.com\/en-us\/um\/people\/nvishno\/site\/Lxb-Web.pdf.  N. Vishnoi. Lx=b. Monograph available at http:\/\/research.microsoft.com\/en-us\/um\/people\/nvishno\/site\/Lxb-Web.pdf."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-297"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"}],"event":{"name":"STOC'13: Symposium on Theory of Computing","location":"Palo Alto California USA","acronym":"STOC'13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488724","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488724","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:21Z","timestamp":1750235961000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488724"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":48,"alternative-id":["10.1145\/2488608.2488724","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488724","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}