{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:20:55Z","timestamp":1755998455111,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":86,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100007224","name":"Connaught Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-18-1-2562"],"award-info":[{"award-number":["N00014-18-1-2562"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1718533"],"award-info":[{"award-number":["1718533"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316410","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"902-913","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Flows in almost linear time via adaptive preconditioning"],"prefix":"10.1145","author":[{"given":"Rasmus","family":"Kyng","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Georgia Tech, USA \/ Microsoft Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Di","family":"Wang","sequence":"additional","affiliation":[{"name":"Georgia Tech, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"STOC. 6 By non-selfloop degree, we mean that self-loops do not count towards the degree of a vertex. STOC \u201919, June 23\u201326","author":"Abraham Ittai","year":"2019","unstructured":"Ittai Abraham and Ofer Neiman . 2012. Using Petal-decompositions to Build a Low Stretch Spanning Tree . In STOC. 6 By non-selfloop degree, we mean that self-loops do not count towards the degree of a vertex. STOC \u201919, June 23\u201326 , 2019 , Phoenix, AZ , USA Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang Ittai Abraham and Ofer Neiman. 2012. Using Petal-decompositions to Build a Low Stretch Spanning Tree. In STOC. 6 By non-selfloop degree, we mean that self-loops do not count towards the degree of a vertex. STOC \u201919, June 23\u201326, 2019, Phoenix, AZ, USA Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310521"},{"key":"e_1_3_2_1_3_1","volume-title":"Orlin","author":"Ahuja Ravindra K.","year":"1993","unstructured":"Ravindra K. Ahuja , Thomas L. Magnanti , and James B . Orlin . 1993 . Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993."},{"volume-title":"algorithms and applications","author":"Network","key":"e_1_3_2_1_4_1","unstructured":"Network flows - theory , algorithms and applications . Prentice Hall . Network flows - theory, algorithms and applications. Prentice Hall."},{"key":"e_1_3_2_1_5_1","unstructured":"Morteza Alamgir and Ulrike V Luxburg. 2011. Phase transition in the family of p-resistances. In Advances in Neural Information Processing Systems. 379\u2013387.   Morteza Alamgir and Ulrike V Luxburg. 2011. Phase transition in the family of p-resistances. In Advances in Neural Information Processing Systems. 379\u2013387."},{"key":"e_1_3_2_1_6_1","volume-title":"Much Faster Algorithms for Matrix Scaling. In Symposium on Foundations of Computer Science (FOCS). 890\u2013901","author":"Allen-Zhu Zeyuan","year":"2017","unstructured":"Zeyuan Allen-Zhu , Yuanzhi Li , Rafael Mendes de Oliveira , and Avi Wigderson . 2017 . Much Faster Algorithms for Matrix Scaling. In Symposium on Foundations of Computer Science (FOCS). 890\u2013901 . Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, and Avi Wigderson. 2017. Much Faster Algorithms for Matrix Scaling. In Symposium on Foundations of Computer Science (FOCS). 890\u2013901."},{"key":"e_1_3_2_1_7_1","unstructured":"Zeyuan Allen Zhu Zhenyu Liao and Lorenzo Orecchia. 2015.  Zeyuan Allen Zhu Zhenyu Liao and Lorenzo Orecchia. 2015."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746610"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_2_1_10_1","unstructured":"David G. Anderson Ming Gu and Christopher Melgaard. 2014.  David G. Anderson Ming Gu and Christopher Melgaard. 2014."},{"key":"e_1_3_2_1_11_1","volume-title":"CoRR abs\/1410.4273","author":"Unweighted Spectral Graph Sparsification An Efficient","year":"2014","unstructured":"An Efficient Algorithm for Unweighted Spectral Graph Sparsification . CoRR abs\/1410.4273 ( 2014 ). An Efficient Algorithm for Unweighted Spectral Graph Sparsification. CoRR abs\/1410.4273 (2014)."},{"key":"e_1_3_2_1_12_1","first-page":"256","article-title":"Experimental Evaluation of Parametric Max-Flow Algorithms","volume":"2007","author":"Babenko Maxim A.","year":"2007","unstructured":"Maxim A. Babenko , Jonathan Derryberry , Andrew V. Goldberg , Robert Endre Tarjan , and Yunhong Zhou . 2007 . Experimental Evaluation of Parametric Max-Flow Algorithms . In WEA 2007 ,. 256 \u2013 269 . Maxim A. Babenko, Jonathan Derryberry, Andrew V. Goldberg, Robert Endre Tarjan, and Yunhong Zhou. 2007. Experimental Evaluation of Parametric Max-Flow Algorithms. In WEA 2007,. 256\u2013269.","journal-title":"WEA"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_3_2_1_14_1","volume-title":"Yin Tat Lee, and Yuanzhi Li","author":"Bubeck S\u00e9bastien","year":"2018","unstructured":"S\u00e9bastien Bubeck , Michael B. Cohen , Yin Tat Lee, and Yuanzhi Li . 2018 . S\u00e9bastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li. 2018."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188776"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422469"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_1_18_1","unstructured":"T. Chu Y. Gao R. Peng S. Sachdeva S. Sawlani and J. Wang. 2018.  T. Chu Y. Gao R. Peng S. Sachdeva S. Sawlani and J. Wang. 2018."},{"key":"e_1_3_2_1_19_1","volume-title":"Short Cycle Decompositions. In IEEE FOCS","author":"Sparsification Graph","year":"2018","unstructured":"Graph Sparsification , Spectral Sketches , and Faster Resistance Computation , via Short Cycle Decompositions. In IEEE FOCS 2018 . 361\u2013372. Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions. In IEEE FOCS 2018. 361\u2013372."},{"key":"e_1_3_2_1_20_1","unstructured":"M. B Cohen J. Kelner R. Kyng J. Peebles R. Peng A. B Rao and A. Sidford. 2018.  M. B Cohen J. Kelner R. Kyng J. Peebles R. Peng A. B Rao and A. Sidford. 2018."},{"key":"e_1_3_2_1_21_1","volume-title":"Sparse LU Factorizations. In IEEE FOCS","author":"Laplacian Solving Directed","year":"2018","unstructured":"Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. In IEEE FOCS 2018 . Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. In IEEE FOCS 2018."},{"key":"e_1_3_2_1_22_1","unstructured":"M. B Cohen J. Kelner J. Peebles R. Peng A. B Rao A. Sidford and A. Vladu. 2017.  M. B Cohen J. Kelner J. Peebles R. Peng A. B Rao A. Sidford and A. Vladu. 2017."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055463"},{"key":"e_1_3_2_1_24_1","unstructured":"M. B. Cohen A. Madry D. Tsipras and A. Vladu. 2017.  M. B. Cohen A. Madry D. Tsipras and A. Vladu. 2017."},{"key":"e_1_3_2_1_25_1","volume-title":"Box Constrained Newton\u2019s Method and Interior Point Methods. In IEEE FOCS","author":"Scaling Matrix","year":"2017","unstructured":"Matrix Scaling and Balancing via Box Constrained Newton\u2019s Method and Interior Point Methods. In IEEE FOCS 2017 . 902\u2013913. Matrix Scaling and Balancing via Box Constrained Newton\u2019s Method and Interior Point Methods. In IEEE FOCS 2017. 902\u2013913."},{"key":"e_1_3_2_1_26_1","volume-title":"Cohen and Richard Peng","author":"Michael","year":"2015","unstructured":"Michael B. Cohen and Richard Peng . 2015 . Michael B. Cohen and Richard Peng. 2015."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746567"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_29_1","volume-title":"trees, and flowers. Canadian Journal of mathematics 17, 3","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds . 1965. Paths , trees, and flowers. Canadian Journal of mathematics 17, 3 ( 1965 ), 449\u2013467. Available at: https:\/\/cms.math.ca\/10.4153\/CJM-1965-045-4. Jack Edmonds. 1965. Paths, trees, and flowers. Canadian Journal of mathematics 17, 3 (1965), 449\u2013467. Available at: https:\/\/cms.math.ca\/10.4153\/CJM-1965-045-4."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_3_2_1_31_1","volume-title":"Conference on Learning Theory. 879\u2013906","author":"Alaoui Ahmed El","year":"2016","unstructured":"Ahmed El Alaoui , Xiang Cheng , Aaditya Ramdas , Martin J Wainwright , and Michael I Jordan . 2016 . Asymptotic behavior of \u2113 p -based Laplacian regularization in semi-supervised learning . In Conference on Learning Theory. 879\u2013906 . Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J Wainwright, and Michael I Jordan. 2016. Asymptotic behavior of \u2113 p -based Laplacian regularization in semi-supervised learning. In Conference on Learning Theory. 879\u2013906."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804394"},{"key":"e_1_3_2_1_34_1","unstructured":"Giorgio Gallo Michael D. Grigoriadis and Robert Endre Tarjan. 1989.  Giorgio Gallo Michael D. Grigoriadis and Robert Endre Tarjan. 1989."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_3_2_1_36_1","volume-title":"Goldberg and Satish Rao","author":"Andrew","year":"1998","unstructured":"Andrew V. Goldberg and Satish Rao . 1998 . Andrew V. Goldberg and Satish Rao. 1998."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_2_1_38_1","volume-title":"Goldberg and Robert Endre Tarjan","author":"Andrew","year":"1988","unstructured":"Andrew V. Goldberg and Robert Endre Tarjan . 1988 . Andrew V. Goldberg and Robert Endre Tarjan. 1988."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628036"},{"key":"e_1_3_2_1_41_1","volume-title":"The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations research 56, 4","author":"Hochbaum Dorit S","year":"2008","unstructured":"Dorit S Hochbaum . 2008. The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations research 56, 4 ( 2008 ), 992\u20131009. Dorit S Hochbaum. 2008. The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations research 56, 4 (2008), 992\u20131009."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21467"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_3_2_1_45_1","first-page":"81","article-title":"O nakhozhdenii maksimal\u0144ogo potoka v setyakh spetsial\u0144ogo vida i nekotorykh prilozheniyakh","volume":"5","author":"Karzanov Alexander V.","year":"1973","unstructured":"Alexander V. Karzanov . 1973 . O nakhozhdenii maksimal\u0144ogo potoka v setyakh spetsial\u0144ogo vida i nekotorykh prilozheniyakh . Matematicheskie Voprosy Upravleniya Proizvodstvom 5 (1973), 81 \u2013 94 . In Russian, title translation: on finding maximum flows in networks with special structure and some applications. Alexander V. Karzanov. 1973. O nakhozhdenii maksimal\u0144ogo potoka v setyakh spetsial\u0144ogo vida i nekotorykh prilozheniyakh. Matematicheskie Voprosy Upravleniya Proizvodstvom 5 (1973), 81\u201394. In Russian, title translation: on finding maximum flows in networks with special structure and some applications.","journal-title":"Matematicheskie Voprosy Upravleniya Proizvodstvom"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"J.A. Kelner and A. Madry. 2009. Faster generation of random spanning trees. In FOCS.   J.A. Kelner and A. Madry. 2009. Faster generation of random spanning trees. In FOCS.","DOI":"10.1109\/FOCS.2009.75"},{"key":"e_1_3_2_1_47_1","volume-title":"Lorenzo Orecchia, and Aaron Sidford.","author":"Kelner Jonathan A.","year":"2014","unstructured":"Jonathan A. Kelner , Yin Tat Lee , Lorenzo Orecchia, and Aaron Sidford. 2014 . An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. In ACM-SIAM SODA 2014. 217\u2013226. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2014. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. In ACM-SIAM SODA 2014. 217\u2013226."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2007.4408910"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2347736.2347759"},{"key":"e_1_3_2_1_52_1","unstructured":"R. Kyng Y. T. Lee R. Peng S. Sachdeva and D. A Spielman. 2016.  R. Kyng Y. T. Lee R. Peng S. Sachdeva and D. A Spielman. 2016."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"e_1_3_2_1_54_1","unstructured":"R. Kyng A. B. Rao S. Sachdeva and D. A Spielman. 2015. Algorithms for Lipschitz learning on graphs. In COLT.  R. Kyng A. B. Rao S. Sachdeva and D. A Spielman. 2015. Algorithms for Lipschitz learning on graphs. In COLT."},{"key":"e_1_3_2_1_55_1","volume-title":"IEEE FOCS","author":"Kyng R.","year":"2016","unstructured":"R. Kyng and S. Sachdeva . 2016. Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple . In IEEE FOCS 2016 . 573\u2013582. R. Kyng and S. Sachdeva. 2016. Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. In IEEE FOCS 2016. 573\u2013582."},{"key":"e_1_3_2_1_56_1","unstructured":"Y. T. Lee R. Peng and D. A. Spielman. 2015. Sparsified Cholesky Solvers for SDD linear systems. CoRR abs\/1506.08204 (2015).  Y. T. Lee R. Peng and D. A. Spielman. 2015. Sparsified Cholesky Solvers for SDD linear systems. CoRR abs\/1506.08204 (2015)."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.24"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Y. T. Lee and A. Sidford. 2014. Path Finding Methods for Linear Programming: Solving Linear Programs in \u02dc O(vrank) Iterations and Faster Algorithms for Maximum Flow. In FOCS.  Y. T. Lee and A. Sidford. 2014. Path Finding Methods for Linear Programming: Solving Linear Programs in \u02dc O(vrank) Iterations and Faster Algorithms for Maximum Flow. In FOCS.","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2012.12.020"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.30"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_62_1","volume-title":"Computing Maximum Flow with Augmenting Electrical Flows. In IEEE FOCS","author":"Madry Aleksander","year":"2016","unstructured":"Aleksander Madry . 2016 . Computing Maximum Flow with Augmenting Electrical Flows. In IEEE FOCS 2016. 593\u2013602. Aleksander Madry. 2016. Computing Maximum Flow with Augmenting Electrical Flows. In IEEE FOCS 2016. 593\u2013602."},{"key":"e_1_3_2_1_63_1","unstructured":"Y. Nesterov and A. Nemirovskii. 1994.  Y. Nesterov and A. Nemirovskii. 1994."},{"key":"e_1_3_2_1_64_1","unstructured":"Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics.  Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"crossref","unstructured":"L. Orecchia S. Sachdeva and N. K. Vishnoi. 2012. Approximating the exponential the lanczos method and an \u02dc O(m)-time spectral algorithm for balanced separator.. In STOC.  L. Orecchia S. Sachdeva and N. K. Vishnoi. 2012. Approximating the exponential the lanczos method and an \u02dc O(m)-time spectral algorithm for balanced separator.. In STOC.","DOI":"10.1145\/2213977.2214080"},{"key":"e_1_3_2_1_66_1","unstructured":"James B. Orlin. 2013.  James B. Orlin. 2013."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_3_2_1_68_1","unstructured":"Bo Peng Lei Zhang and David Zhang. 2013.  Bo Peng Lei Zhang and David Zhang. 2013."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2012.09.015"},{"key":"e_1_3_2_1_70_1","unstructured":"Richard Peng. 2016.  Richard Peng. 2016."},{"key":"e_1_3_2_1_71_1","volume-title":"ACM-SIAM SODA 2016. 1862","author":"Approximate","year":"1867","unstructured":"Approximate undirected maximum flows in O(m polylog(n)) time . In ACM-SIAM SODA 2016. 1862 \u2013 1867 . Approximate undirected maximum flows in O(m polylog(n)) time. In ACM-SIAM SODA 2016. 1862\u20131867."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591832"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374415"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(92)90242-F"},{"key":"e_1_3_2_1_75_1","first-page":"2616","article-title":"Expander Decomposition and Pruning","volume":"2019","author":"Saranurak Thatchaphol","year":"2019","unstructured":"Thatchaphol Saranurak and Di Wang . 2019 . Expander Decomposition and Pruning : Faster, Stronger, and Simpler. In ACM-SIAM SODA 2019. 2616 \u2013 2635 . Thatchaphol Saranurak and Di Wang. 2019. Expander Decomposition and Pruning: Faster, Stronger, and Simpler. In ACM-SIAM SODA 2019. 2616\u20132635.","journal-title":"Faster, Stronger, and Simpler. In ACM-SIAM SODA"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188852"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100259"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055501"},{"key":"e_1_3_2_1_80_1","volume-title":"Generalized Preconditioning and Undirected Minimum-cost Flow. In ACM-SIAM SODA","author":"Sherman J.","year":"2017","unstructured":"J. Sherman . 2017 . Generalized Preconditioning and Undirected Minimum-cost Flow. In ACM-SIAM SODA 2017. J. Sherman. 2017. Generalized Preconditioning and Undirected Minimum-cost Flow. In ACM-SIAM SODA 2017."},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"crossref","unstructured":"D.A. Spielman and S. Teng. 2004.  D.A. Spielman and S. Teng. 2004.","DOI":"10.1046\/j.1039-8562.2003.02063.x"},{"key":"e_1_3_2_1_84_1","unstructured":"Nearly-linear Time Algorithms for Graph Partitioning Graph Sparsification and Solving Linear Systems. In STOC.  Nearly-linear Time Algorithms for Graph Partitioning Graph Sparsification and Solving Linear Systems. In STOC."},{"key":"e_1_3_2_1_85_1","unstructured":"D. Spielman and S. Teng. 2014.  D. Spielman and S. Teng. 2014."},{"key":"e_1_3_2_1_86_1","series-title":"SIAM J. Matrix Anal. Appl. 35, 3","volume-title":"Diagonally Dominant Linear Systems","author":"Time Nearly Linear","year":"2014","unstructured":"Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric , Diagonally Dominant Linear Systems . SIAM J. Matrix Anal. Appl. 35, 3 ( 2014 ), 835\u2013885. Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM J. Matrix Anal. Appl. 35, 3 (2014), 835\u2013885."}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316410","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316410","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316410","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:33Z","timestamp":1750204473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316410"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":86,"alternative-id":["10.1145\/3313276.3316410","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316410","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}