{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T22:09:56Z","timestamp":1781820596184,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1111109,1553428,1122374,1637566,1065125"],"award-info":[{"award-number":["1111109,1553428,1122374,1637566,1065125"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055463","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"410-419","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs"],"prefix":"10.1145","author":[{"given":"Michael B.","family":"Cohen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Kelner","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Peebles","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anup B.","family":"Rao","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adrian","family":"Vladu","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"On Fully Dynamic Graph Sparsifiers. CoRR abs\/1604.02094","author":"Abraham Ittai","year":"2016","unstructured":"Ittai Abraham , David Durfee , Ioannis Koutis , Sebastian Krinninger , and Richard Peng . 2016. On Fully Dynamic Graph Sparsifiers. CoRR abs\/1604.02094 ( 2016 ). Available at: http:\/\/arxiv.org\/abs\/1604.02094. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. 2016. On Fully Dynamic Graph Sparsifiers. CoRR abs\/1604.02094 (2016). Available at: http:\/\/arxiv.org\/abs\/1604.02094."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777892"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.12.041"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of The 28th Conference on Learning Theory","author":"Cheng Dehua","year":"2015","unstructured":"Dehua Cheng , Yu Cheng , Yan Liu , Richard Peng , and Shang-Hua Teng . 2015 . Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification . Proceedings of The 28th Conference on Learning Theory (2015), 364\u2013390. Available at http:\/\/jmlr.org\/proceedings\/papers\/v40\/Cheng15.pdf. Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng. 2015. Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification. Proceedings of The 28th Conference on Learning Theory (2015), 364\u2013390. Available at http:\/\/jmlr.org\/proceedings\/papers\/v40\/Cheng15.pdf."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0237-z"},{"key":"e_1_3_2_1_9_1","volume-title":"WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings. 203\u2013219","author":"Chung Fan","year":"2013","unstructured":"Fan Chung and Olivia Simpson . 2013 . Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank. In Algorithms and Models for the Web Graph - 10th International Workshop , WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings. 203\u2013219 . Fan Chung and Olivia Simpson. 2013. Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank. In Algorithms and Models for the Web Graph - 10th International Workshop, WAW 2013, Cambridge, MA, USA, December 14-15, 2013, Proceedings. 203\u2013219."},{"key":"e_1_3_2_1_10_1","volume-title":"IWOCA 2014","author":"Chung Fan","year":"2014","unstructured":"Fan Chung and Olivia Simpson . 2014 . Computing Heat Kernel Pagerank and a Local Clustering Algorithm. In Combinatorial Algorithms - 25th International Workshop , IWOCA 2014 , Duluth, MN, USA , October 15-17, 2014, Revised Selected Papers. 110\u2013121. Fan Chung and Olivia Simpson. 2014. Computing Heat Kernel Pagerank and a Local Clustering Algorithm. In Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers. 110\u2013121."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18009-5_2"},{"key":"e_1_3_2_1_12_1","volume-title":"Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs. CoRR abs\/1611.00755","author":"Cohen Michael B.","year":"2016","unstructured":"Michael B. Cohen , Jonathan A. Kelner , John Peebles , Richard Peng , Anup Rao , Aaron Sidford , and Adrian Vladu . 2016. Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs. CoRR abs\/1611.00755 ( 2016 ). http:\/\/arxiv.org\/abs\/1611.00755 Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu. 2016. Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs. CoRR abs\/1611.00755 (2016). http:\/\/arxiv.org\/abs\/1611.00755"},{"key":"e_1_3_2_1_13_1","volume-title":"Simulating Random Walks, and More. arXiv preprint arXiv:1608.03270","author":"Cohen Michael B.","year":"2016","unstructured":"Michael B. Cohen , Jonathan A. Kelner , John Peebles , Richard Peng , Aaron Sidford , and Adrian Vladu . 2016. Faster Algorithms for Computing the Stationary Distribution , Simulating Random Walks, and More. arXiv preprint arXiv:1608.03270 ( 2016 ). Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. 2016. Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More. arXiv preprint arXiv:1608.03270 (2016)."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_1_15_1","volume-title":"Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in \u00d5(m10\/7 log W) Time. CoRR abs\/1605.01717","author":"Cohen Michael B.","year":"2016","unstructured":"Michael B. Cohen , Aleksander Madry , Piotr Sankowski , and Adrian Vladu . 2016. Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in \u00d5(m10\/7 log W) Time. CoRR abs\/1605.01717 ( 2016 ). http:\/\/arxiv.org\/abs\/1605. Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu. 2016. Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in \u00d5(m10\/7 log W) Time. CoRR abs\/1605.01717 (2016). http:\/\/arxiv.org\/abs\/1605."},{"key":"e_1_3_2_1_16_1","unstructured":"01717  01717"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897654"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_3_2_1_19_1","volume-title":"An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials. arXiv preprint arXiv:1507.07497","author":"Jindal Gorav","year":"2015","unstructured":"Gorav Jindal and Pavel Kolev . 2015. An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials. arXiv preprint arXiv:1507.07497 ( 2015 ). Gorav Jindal and Pavel Kolev. 2015. An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials. arXiv preprint arXiv:1507.07497 (2015)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195422"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509918"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"e_1_3_2_1_27_1","volume-title":"Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple. CoRR abs\/1605.02353","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng and Sushant Sachdeva . 2016. Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple. CoRR abs\/1605.02353 ( 2016 ). http: \/\/arxiv.org\/abs\/1605.02353 Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple. CoRR abs\/1605.02353 (2016). http: \/\/arxiv.org\/abs\/1605.02353"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.24"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.24"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_32_1","volume-title":"Computing Maximum Flow with Augmenting Electrical Flows. CoRR abs\/1608.06016","author":"Madry Aleksander","year":"2016","unstructured":"Aleksander Madry . 2016. Computing Maximum Flow with Augmenting Electrical Flows. CoRR abs\/1608.06016 ( 2016 ). http:\/\/arxiv.org\/abs\/1608.06016 Aleksander Madry. 2016. Computing Maximum Flow with Augmenting Electrical Flows. CoRR abs\/1608.06016 (2016). http:\/\/arxiv.org\/abs\/1608.06016"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591832"},{"key":"e_1_3_2_1_34_1","volume-title":"Iterative Methods for Sparse Linear Systems","author":"Saad Yousef","unstructured":"Yousef Saad . 2003. Iterative Methods for Sparse Linear Systems ( 2 nd ed.). Society for Industrial and Applied Mathematics , Philadelphia, PA, USA . Available at: http:\/\/www-users.cs.umn.edu\/~saad\/toc.pdf. Yousef Saad. 2003. Iterative Methods for Sparse Linear Systems (2nd ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. Available at: http:\/\/www-users.cs.umn.edu\/~saad\/toc.pdf.","edition":"2"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_1_38_1","volume-title":"Introduction to the numerical solutions of Markov chains","author":"Stewart Williams J","unstructured":"Williams J Stewart . 1994. Introduction to the numerical solutions of Markov chains . Princeton Univ. Press . Williams J Stewart. 1994. Introduction to the numerical solutions of Markov chains. Princeton Univ. Press."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13562-0_2"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055463","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055463","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":39,"alternative-id":["10.1145\/3055399.3055463","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055463","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}