{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T17:52:29Z","timestamp":1786211549191,"version":"3.56.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,5,31]],"date-time":"2014-05-31T00:00:00Z","timestamp":1401494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1111257, CCF-1018463, CCF-1018463, CCF-1065106"],"award-info":[{"award-number":["CCF-1111257, CCF-1018463, CCF-1018463, CCF-1065106"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-12-1-0175"],"award-info":[{"award-number":["FA9550-12-1-0175"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,5,31]]},"DOI":"10.1145\/2591796.2591833","type":"proceedings-article","created":{"date-parts":[[2015,10,1]],"date-time":"2015-10-01T12:01:58Z","timestamp":1443700918000},"page":"343-352","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["Solving SDD linear systems in nearly\n            <i>m<\/i>\n            log\n            <sup>1\/2<\/sup>\n            <i>n<\/i>\n            time"],"prefix":"10.1145","author":[{"given":"Michael B.","family":"Cohen","sequence":"first","affiliation":[{"name":"M.I.T."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Kyng","sequence":"additional","affiliation":[{"name":"Yale University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub W.","family":"Pachocki","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"M.I.T."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anup B.","family":"Rao","sequence":"additional","affiliation":[{"name":"Yale University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shen Chen","family":"Xu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,5,31]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.62"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_3_2_2_9_1","volume-title":"Sandia National Lab.","author":"Boman E.","year":"2001","unstructured":"E. Boman and B. Hendrickson . On spanning tree preconditioners. Manuscript , Sandia National Lab. , 2001 . E. Boman and B. Hendrickson. On spanning tree preconditioners. Manuscript, Sandia National Lab., 2001."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/040611781"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422469"},{"key":"e_1_3_2_2_12_1","volume-title":"Applications of spectral algorithms for image processing tasks","author":"Chin H. H.","year":"2012","unstructured":"H. H. Chin and G. L. Miller . Applications of spectral algorithms for image processing tasks . 2012 . H. H. Chin and G. L. Miller. Applications of spectral algorithms for image processing tasks. 2012."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070469"},{"key":"e_1_3_2_2_15_1","volume-title":"Preconditioning in expectation. CoRR, abs\/1401.6236","author":"Cohen M. B.","year":"2014","unstructured":"M. B. Cohen , R. Kyng , J. W. Pachocki , R. Peng , and A. Rao . Preconditioning in expectation. CoRR, abs\/1401.6236 , 2014 . M. B. Cohen, R. Kyng, J. W. Pachocki, R. Peng, and A. Rao. Preconditioning in expectation. CoRR, abs\/1401.6236, 2014."},{"key":"e_1_3_2_2_16_1","volume-title":"Stretching stretch. CoRR, abs\/1401.2454","author":"Cohen M. B.","year":"2014","unstructured":"M. B. Cohen , G. L. Miller , J. W. Pachocki , R. Peng , and S. C. Xu . Stretching stretch. CoRR, abs\/1401.2454 , 2014 . M. B. Cohen, G. L. Miller, J. W. Pachocki, R. Peng, and S. C. Xu. Stretching stretch. CoRR, abs\/1401.2454, 2014."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/050641661"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.001"},{"key":"e_1_3_2_2_21_1","volume-title":"Randomized algorithms, winter","author":"Harvey N.","year":"2011","unstructured":"N. Harvey . C& O 750 : Randomized algorithms, winter 2011 , lecture 11 notes. 2011. N. Harvey. C&O 750: Randomized algorithms, winter 2011, lecture 11 notes. 2011."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213979"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806699"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_2_27_1","volume-title":"Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. CoRR, abs\/1305.1922","author":"Lee Y. T.","year":"2013","unstructured":"Y. T. Lee and A. Sidford . Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. CoRR, abs\/1305.1922 , 2013 . Y. T. Lee and A. Sidford. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. CoRR, abs\/1305.1922, 2013."},{"key":"e_1_3_2_2_28_1","volume-title":"from ows to matchings, and back. CoRR, abs\/1307.2205","author":"Madry A.","year":"2013","unstructured":"A. Madry . Navigating central path with electrical ows : from ows to matchings, and back. CoRR, abs\/1307.2205 , 2013 . A. Madry. Navigating central path with electrical ows: from ows to matchings, and back. CoRR, abs\/1307.2205, 2013."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627900"},{"key":"e_1_3_2_2_30_1","volume-title":"Assouad's theorem with dimension independent of the snowflaking. arXiv preprint arXiv:1012.2307","author":"Naor A.","year":"2010","unstructured":"A. Naor and O. Neiman . Assouad's theorem with dimension independent of the snowflaking. arXiv preprint arXiv:1012.2307 , 2010 . A. Naor and O. Neiman. Assouad's theorem with dimension independent of the snowflaking. arXiv preprint arXiv:1012.2307, 2010."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214080"},{"key":"e_1_3_2_2_33_1","volume-title":"An efficient parallel solver for SDD linear systems. CoRR, abs\/1311.3286","author":"Peng R.","year":"2013","unstructured":"R. Peng and D. A. Spielman . An efficient parallel solver for SDD linear systems. CoRR, abs\/1311.3286 , 2013 . R. Peng and D. A. Spielman. An efficient parallel solver for SDD linear systems. CoRR, abs\/1311.3286, 2013."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081089408818331"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_3_2_2_37_1","first-page":"416","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS '03","author":"Spielman D. A.","unstructured":"D. A. Spielman and S.-H. Teng . Solving sparse, symmetric, diagonally-dominant linear systems in time O(m1.31) . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS '03 , pages 416 --, Washington, DC, USA, 2003. IEEE Computer Society. D. A. Spielman and S.-H. Teng. Solving sparse, symmetric, diagonally-dominant linear systems in time O(m1.31). In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS '03, pages 416--, Washington, DC, USA, 2003. IEEE Computer Society."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_2_39_1","volume-title":"Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105","author":"Spielman D. A.","year":"2008","unstructured":"D. A. Spielman and S.-H. Teng . Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105 , 2008 . Available at http:\/\/www.arxiv.org\/abs\/cs.NA\/0607105. Submitted to SIMAX. D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105, 2008. Available at http:\/\/www.arxiv.org\/abs\/cs.NA\/0607105. Submitted to SIMAX."},{"key":"e_1_3_2_2_40_1","volume-title":"A note on preconditioning by low-stretch spanning trees. CoRR, abs\/0903.2816","author":"Spielman D. A.","year":"2009","unstructured":"D. A. Spielman and J. Woo . A note on preconditioning by low-stretch spanning trees. CoRR, abs\/0903.2816 , 2009 . D. A. Spielman and J. Woo. A note on preconditioning by low-stretch spanning trees. CoRR, abs\/0903.2816, 2009."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1080"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"e_1_3_2_2_43_1","volume-title":"October","author":"Vaidya P. M.","year":"1991","unstructured":"P. M. Vaidya . Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation , October 1991 . P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_71"}],"event":{"name":"STOC '14: Symposium on Theory of Computing","location":"New York New York","acronym":"STOC '14","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591833","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2591796.2591833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:55:45Z","timestamp":1750229745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591833"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,31]]},"references-count":42,"alternative-id":["10.1145\/2591796.2591833","10.1145\/2591796"],"URL":"https:\/\/doi.org\/10.1145\/2591796.2591833","relation":{},"subject":[],"published":{"date-parts":[[2014,5,31]]},"assertion":[{"value":"2014-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}