{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:14:35Z","timestamp":1787494475408,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":36,"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\/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\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000870","name":"John D. and Catherine T. MacArthur Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000870","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.2591832","type":"proceedings-article","created":{"date-parts":[[2015,10,1]],"date-time":"2015-10-01T08:01:58Z","timestamp":1443686518000},"page":"333-342","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["An efficient parallel solver for SDD linear systems"],"prefix":"10.1145","author":[{"given":"Richard","family":"Peng","sequence":"first","affiliation":[{"name":"M.I.T."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel A.","family":"Spielman","sequence":"additional","affiliation":[{"name":"Yale 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.1017\/CBO9780511624100"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384019"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989496"},{"key":"e_1_3_2_2_4_1","volume-title":"Sandia National Lab.","author":"Boman Erik","year":"2001","unstructured":"{BH01} Erik Boman and B. Hendrickson . On spanning tree preconditioners. Manuscript , Sandia National Lab. , 2001 . {BH01} Erik Boman and B. Hendrickson. On spanning tree preconditioners. Manuscript, Sandia National Lab., 2001."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801390637"},{"key":"e_1_3_2_2_6_1","volume-title":"A Multigrid Tutorial","author":"Briggs W. L.","year":"2001","unstructured":"{BHM01} W. L. Briggs , V. E. Henson , and S. F. McCormick . A Multigrid Tutorial , 2 nd Edition. SIAM , 2001 . {BHM01} W. L. Briggs, V. E. Henson, and S. F. McCormick. A Multigrid Tutorial, 2nd Edition. SIAM, 2001.","edition":"2"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/040611781"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9396-1"},{"key":"e_1_3_2_2_13_1","first-page":"1002","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Koutis Ioannis","year":"2007","unstructured":"{KM07} Ioannis Koutis and Gary L. Miller . A linear work, o(n1\/6) time, parallel algorithm for solving planar Laplacians . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1002 -- 1011 , 2007 . {KM07} Ioannis Koutis and Gary L. Miller. A linear work, o(n1\/6) time, parallel algorithm for solving planar Laplacians. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1002--1011, 2007."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748019"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213979"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2011.05.013"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_2_20_1","volume-title":"A simple parallel algorithm for spectral sparsification. arXiv preprint arXiv:1402.3851","author":"Koutis Ioannis","year":"2014","unstructured":"{Kou14} Ioannis Koutis . A simple parallel algorithm for spectral sparsification. arXiv preprint arXiv:1402.3851 , 2014 . {Kou14} Ioannis Koutis. A simple parallel algorithm for spectral sparsification. arXiv preprint arXiv:1402.3851, 2014."},{"key":"e_1_3_2_2_21_1","volume-title":"Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Levin Alex","year":"2012","unstructured":"{LKP12} Alex Levin , Ioannis Koutis , and Richard Peng . Improved spectral sparsification and numerical algorithms for sdd matrices . In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS) , 2012 . to appear. {LKP12} Alex Levin, Ioannis Koutis, and Richard Peng. Improved spectral sparsification and numerical algorithms for sdd matrices. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS), 2012. to appear."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.24"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214080"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133078"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(98)00191-6"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jfan.1998.3384"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/829576"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"e_1_3_2_2_33_1","series-title":"SIAM Journal on Matrix Analysis and Applications","volume-title":"Spielman and Shang-Hua Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems","author":"Daniel","year":"2014","unstructured":"{ST14} Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems . SIAM Journal on Matrix Analysis and Applications , 2014 . to appear. {ST14} Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications, 2014. to appear."},{"key":"e_1_3_2_2_34_1","volume-title":"Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC","author":"Vaidya Pravin M.","year":"1990","unstructured":"{Vai90} Pravin 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. {Vai90} Pravin 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_2_35_1","first-page":"321","volume-title":"Adv. in Neural Inf. Proc. Sys. 16","author":"Zhou Dengyong","year":"2003","unstructured":"{ZBL+03} Dengyong Zhou , Olivier Bousquet , Thomas Navin Lal , Jason Weston , and Bernhard Sch\u00f6lkopf . Learning with local and global consistency . In Adv. in Neural Inf. Proc. Sys. 16 , pages 321 -- 328 , 2003 . {ZBL+03} Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Sch\u00f6lkopf. Learning with local and global consistency. In Adv. in Neural Inf. Proc. Sys. 16, pages 321--328, 2003."},{"key":"e_1_3_2_2_36_1","volume-title":"Proc. 20th Int. Conf. on Mach. Learn.","author":"Zhu Xiaojin","year":"2003","unstructured":"{ZGL03} Xiaojin Zhu , Zoubin Ghahramani , and John D. Lafferty . Semi-supervised learning using Gaussian fields and harmonic functions . In Proc. 20th Int. Conf. on Mach. Learn. , 2003 . {ZGL03} Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In Proc. 20th Int. Conf. on Mach. Learn., 2003."},{"key":"e_1_3_2_2_37_1","first-page":"132","volume-title":"ICML Workshop on Statistical Relational Learning and Its Connections to Other Fields","author":"Zhou Dengyong","year":"2004","unstructured":"{ZS04} Dengyong Zhou and Bernhard Sch\u00f6lkopf . A regularization framework for learning from graph data . In ICML Workshop on Statistical Relational Learning and Its Connections to Other Fields , pages 132 -- 137 , 2004 . {ZS04} Dengyong Zhou and Bernhard Sch\u00f6lkopf. A regularization framework for learning from graph data. In ICML Workshop on Statistical Relational Learning and Its Connections to Other Fields, pages 132--137, 2004."}],"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.2591832","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2591796.2591832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:55:45Z","timestamp":1750215345000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,31]]},"references-count":36,"alternative-id":["10.1145\/2591796.2591832","10.1145\/2591796"],"URL":"https:\/\/doi.org\/10.1145\/2591796.2591832","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"}}]}}