{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:16:56Z","timestamp":1767853016315,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":75,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520068","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"543-556","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Faster maxflow via improved dynamic spectral vertex sparsifiers"],"prefix":"10.1145","author":[{"given":"Jan","family":"van den Brand","sequence":"first","affiliation":[{"name":"Simons Institute for the Theory of Computing Berkeley, USA \/ University of California at Berkeley, USA"}]},{"given":"Yu","family":"Gao","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}]},{"given":"Arun","family":"Jambulapati","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}]},{"given":"Yang P.","family":"Liu","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.86"},{"key":"e_1_3_2_1_2_1","volume-title":"Stochastic Bias-Reduced Gradient Methods. Advances in Neural Information Processing Systems, 34","author":"Asi Hilal","year":"2021","unstructured":"Hilal Asi , Yair Carmon , Arun Jambulapati , Yujia Jin , and Aaron Sidford . 2021. Stochastic Bias-Reduced Gradient Methods. Advances in Neural Information Processing Systems, 34 ( 2021 ). Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. 2021. Stochastic Bias-Reduced Gradient Methods. Advances in Neural Information Processing Systems, 34 (2021)."},{"key":"e_1_3_2_1_3_1","volume-title":"Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs","author":"Axiotis Kyriakos","unstructured":"Kyriakos Axiotis , Aleksander Madry , and Adrian Vladu . 2020. Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs . In FOCS. IEEE , 93\u2013104. Available at: arxiv:2111.10368v1 Kyriakos Axiotis, Aleksander Madry, and Adrian Vladu. 2020. Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs. In FOCS. IEEE, 93\u2013104. Available at: arxiv:2111.10368v1"},{"key":"e_1_3_2_1_4_1","volume-title":"Faster Sparse Minimum Cost Flow by Electrical Flow Localization","author":"Axiotis Kyriakos","unstructured":"Kyriakos Axiotis , Aleksander M\u0105dry , and Adrian Vladu . 2021. Faster Sparse Minimum Cost Flow by Electrical Flow Localization . In FOCS. IEEE. Kyriakos Axiotis, Aleksander M\u0105dry, and Adrian Vladu. 2021. Faster Sparse Minimum Cost Flow by Electrical Flow Localization. In FOCS. IEEE."},{"key":"e_1_3_2_1_5_1","volume-title":"Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds. CoRR, abs\/2111.03980","author":"Beimel Amos","year":"2021","unstructured":"Amos Beimel , Haim Kaplan , Yishay Mansour , Kobbi Nissim , Thatchaphol Saranurak , and Uri Stemmer . 2021. Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds. CoRR, abs\/2111.03980 ( 2021 ). Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. 2021. Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds. CoRR, abs\/2111.03980 (2021)."},{"key":"e_1_3_2_1_6_1","volume-title":"Adversarially Robust Streaming via Dense-Sparse Trade-offs. CoRR, abs\/2109.03785","author":"Ben-Eliezer Omri","year":"2021","unstructured":"Omri Ben-Eliezer , Talya Eden , and Krzysztof Onak . 2021. Adversarially Robust Streaming via Dense-Sparse Trade-offs. CoRR, abs\/2109.03785 ( 2021 ). Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. 2021. Adversarially Robust Streaming via Dense-Sparse Trade-offs. CoRR, abs\/2109.03785 (2021)."},{"key":"e_1_3_2_1_7_1","volume-title":"Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun.","author":"Bernstein Aaron","year":"2020","unstructured":"Aaron Bernstein , Jan van den Brand , Maximilian Probst Gutenberg , Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. 2020 . Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. CoRR , abs\/2004.08432 (2020), Available at arxiv:2004.08432 Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. 2020. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. CoRR, abs\/2004.08432 (2020), Available at arxiv:2004.08432"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897521"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039715"},{"key":"e_1_3_2_1_10_1","volume-title":"Maximilian Probst Gutenberg, and Thatchaphol Saranurak","author":"Bernstein Aaron","year":"2021","unstructured":"Aaron Bernstein , Maximilian Probst Gutenberg, and Thatchaphol Saranurak . 2021 . Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time . arXiv preprint arXiv:2101.07149. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. 2021. Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. arXiv preprint arXiv:2101.07149."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/WSC.2015.7408524"},{"key":"e_1_3_2_1_12_1","volume-title":"A Deterministic Linear Program Solver in Current Matrix Multiplication Time","author":"van den Brand Jan","unstructured":"Jan van den Brand . 2020. A Deterministic Linear Program Solver in Current Matrix Multiplication Time . In SODA. SIAM , 259\u2013278. Jan van den Brand. 2020. A Deterministic Linear Program Solver in Current Matrix Multiplication Time. In SODA. SIAM, 259\u2013278."},{"key":"e_1_3_2_1_13_1","volume-title":"Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms","author":"van den Brand Jan","unstructured":"Jan van den Brand . 2021. Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms . In SOSA. SIAM , 1\u201313. Jan van den Brand. 2021. Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms. In SOSA. SIAM, 1\u201313."},{"key":"e_1_3_2_1_14_1","volume-title":"Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.","author":"van den Brand Jan","year":"2021","unstructured":"Jan van den Brand , Yin Tat Lee , Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. 2021 . Minimum cost flows, MDPs, and \u2113 _1-regression in nearly linear time for dense instances. In STOC. ACM , 859\u2013869. Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. 2021. Minimum cost flows, MDPs, and \u2113 _1-regression in nearly linear time for dense instances. In STOC. ACM, 859\u2013869."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00090"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384309"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451025"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00111"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316320"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316303"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039734"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_25_1","volume-title":"Richard Peng, Sushant Sachdeva, and Guanghao Ye.","author":"Dong Sally","year":"2022","unstructured":"Sally Dong , Yu Gao , Gramoz Goranci , Yin Tat Lee , Richard Peng, Sushant Sachdeva, and Guanghao Ye. 2022 . Nested Dissection Meets IPMs : Planar Min-Cost Flow in Nearly-Linear Time. In SODA. SIAM. Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Guanghao Ye. 2022. Nested Dissection Meets IPMs : Planar Min-Cost Flow in Nearly-Linear Time. In SODA. SIAM."},{"key":"e_1_3_2_1_26_1","volume-title":"Yin Tat Lee, and Guanghao Ye","author":"Dong Sally","year":"2021","unstructured":"Sally Dong , Yin Tat Lee, and Guanghao Ye . 2021 . A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path. In STOC. ACM , 1784\u20131797. Sally Dong, Yin Tat Lee, and Guanghao Ye. 2021. A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path. In STOC. ACM, 1784\u20131797."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316379"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055499"},{"key":"e_1_3_2_1_29_1","first-page":"3","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth . 2014 . The algorithmic foundations of differential privacy .. Found. Trends Theor. Comput. Sci. , 9 , 3 - 4 (2014), 211\u2013407. Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy.. Found. Trends Theor. Comput. Sci., 9, 3-4 (2014), 211\u2013407.","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_3_2_1_31_1","volume-title":"FOCS","author":"Gao Yu","year":"2021","unstructured":"Yu Gao , Yang P Liu , and Richard Peng . 2021 . Fully dynamic electrical flows: sparse maxflow faster than Goldberg-Rao . FOCS 2021, Available at arxiv:2101.07233 Yu Gao, Yang P Liu, and Richard Peng. 2021. Fully dynamic electrical flows: sparse maxflow faster than Goldberg-Rao. FOCS 2021, Available at arxiv:2101.07233"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096249291500001X"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.3.430"},{"key":"e_1_3_2_1_35_1","volume-title":"Adaptive Machine Unlearning. CoRR, abs\/2106.04378","author":"Gupta Varun","year":"2021","unstructured":"Varun Gupta , Christopher Jung , Seth Neel , Aaron Roth , Saeed Sharifi-Malvajerdi , and Chris Waites . 2021. Adaptive Machine Unlearning. CoRR, abs\/2106.04378 ( 2021 ). Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites. 2021. Adaptive Machine Unlearning. CoRR, abs\/2106.04378 (2021)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.154"},{"key":"e_1_3_2_1_37_1","unstructured":"Avinatan Hassidim Haim Kaplan Yishay Mansour Yossi Matias and Uri Stemmer. 2020. Adversarially Robust Streaming Algorithms via Differential Privacy. In NeurIPS.  Avinatan Hassidim Haim Kaplan Yishay Mansour Yossi Matias and Uri Stemmer. 2020. Adversarially Robust Streaming Algorithms via Differential Privacy. In NeurIPS."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.33"},{"key":"e_1_3_2_1_39_1","volume-title":"Faster Dynamic Matrix Inverse for Faster LPs. CoRR, abs\/2004.07470","author":"Jiang Shunhua","year":"2020","unstructured":"Shunhua Jiang , Zhao Song , Omri Weinstein , and Hengjie Zhang . 2020. Faster Dynamic Matrix Inverse for Faster LPs. CoRR, abs\/2004.07470 ( 2020 ), arxiv:2004.07470 Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. 2020. Faster Dynamic Matrix Inverse for Faster LPs. CoRR, abs\/2004.07470 (2020), arxiv:2004.07470"},{"key":"e_1_3_2_1_40_1","volume-title":"Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011","author":"Kane Daniel M.","year":"2011","unstructured":"Daniel M. Kane , Jelani Nelson , Ely Porat , and David P. Woodruff . 2011. Fast moment estimation in data streams in optimal space . In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011 , San Jose, CA, USA , June 6-8 2011 . ACM, 745\u2013754. Available at arxiv:1007.4191 Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff. 2011. Fast moment estimation in data streams in optimal space. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, June 6-8 2011. ACM, 745\u2013754. Available at arxiv:1007.4191"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_3_2_1_42_1","first-page":"81","article-title":"On finding maximum flows in networks with special structure and some applications","volume":"5","author":"Karzanov Alexander V","year":"1973","unstructured":"Alexander V Karzanov . 1973 . On finding maximum flows in networks with special structure and some applications . Matematicheskie Voprosy Upravleniya Proizvodstvom , 5 (1973), 81 \u2013 94 . Alexander V Karzanov. 1973. On finding maximum flows in networks with special structure and some applications. Matematicheskie Voprosy Upravleniya Proizvodstvom, 5 (1973), 81\u201394.","journal-title":"Matematicheskie Voprosy Upravleniya Proizvodstvom"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00020"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634090"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.75"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_1_47_1","volume-title":"Approaching Optimality for Solving SDD Linear Systems. In 51th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2010","author":"Koutis Ioannis","year":"2010","unstructured":"Ioannis Koutis , Gary L. Miller , and Richard Peng . 2010 . Approaching Optimality for Solving SDD Linear Systems. In 51th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2010 , Las Vegas, NV, USA , October 23-26, 2010. 235\u2013244. Available at arxiv:1003.2958 Ioannis Koutis, Gary L. Miller, and Richard Peng. 2010. Approaching Optimality for Solving SDD Linear Systems. In 51th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, NV, USA, October 23-26, 2010. 235\u2013244. Available at arxiv:1003.2958"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_49_1","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng , Yin Tat Lee , Richard Peng , Sushant Sachdeva , and Daniel A. Spielman . 2016. Sparsified Cholesky and multigrid solvers for connection Laplacians . In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 , Cambridge, MA, USA , June 18-21, 2016 . 842\u2013850. Available at arxiv:1512.01892 Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. 2016. Sparsified Cholesky and multigrid solvers for connection Laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. 842\u2013850. Available at arxiv:1512.01892"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316410"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488704"},{"key":"e_1_3_2_1_53_1","volume-title":"Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In 2013 ieee 54th annual symposium on foundations of computer science. 147\u2013156","author":"Lee Yin Tat","unstructured":"Yin Tat Lee and Aaron Sidford . 2013. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In 2013 ieee 54th annual symposium on foundations of computer science. 147\u2013156 . Yin Tat Lee and Aaron Sidford. 2013. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In 2013 ieee 54th annual symposium on foundations of computer science. 147\u2013156."},{"key":"e_1_3_2_1_54_1","volume-title":"Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee and Aaron Sidford . 2015 . Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 , Berkeley, CA, USA , October 17-20, 2015. IEEE Computer Society, 230\u2013249. Available at arxiv:1503.01752 Yin Tat Lee and Aaron Sidford. 2015. Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, October 17-20, 2015. IEEE Computer Society, 230\u2013249. Available at arxiv:1503.01752"},{"key":"e_1_3_2_1_55_1","volume-title":"Solving Linear Programs with Sqrt(rank) Linear System Solves. CoRR, abs\/1910.08033","author":"Lee Yin Tat","year":"2019","unstructured":"Yin Tat Lee and Aaron Sidford . 2019. Solving Linear Programs with Sqrt(rank) Linear System Solves. CoRR, abs\/1910.08033 ( 2019 ), arxiv:1910.08033. arxiv:1910.08033 Yin Tat Lee and Aaron Sidford. 2019. Solving Linear Programs with Sqrt(rank) Linear System Solves. CoRR, abs\/1910.08033 (2019), arxiv:1910.08033. arxiv:1910.08033"},{"key":"e_1_3_2_1_56_1","volume-title":"Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. In Conference on Learning Theory, COLT 2019","author":"Lee Yin Tat","year":"2019","unstructured":"Yin Tat Lee , Zhao Song , and Qiuyi Zhang . 2019 . Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. In Conference on Learning Theory, COLT 2019 , Phoenix, AZ, USA , June 25-28, 2019 (Proceedings of Machine Learning Research, Vol. 99). PMLR, 2140\u20132157. Available at arxiv:1905.04447 Yin Tat Lee, Zhao Song, and Qiuyi Zhang. 2019. Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. In Conference on Learning Theory, COLT 2019, Phoenix, AZ, USA, June 25-28, 2019 (Proceedings of Machine Learning Research, Vol. 99). PMLR, 2140\u20132157. Available at arxiv:1905.04447"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00044"},{"key":"e_1_3_2_1_58_1","volume-title":"Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020","author":"Yang","year":"2020","unstructured":"Yang P. Liu and Aaron Sidford. 2020. Faster energy maximization for faster maximum flow . In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 , Chicago, IL, USA , June 22-26, 2020 . ACM, 803\u2013814. Available at arxiv:1910.14276 Yang P. Liu and Aaron Sidford. 2020. Faster energy maximization for faster maximum flow. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. ACM, 803\u2013814. Available at arxiv:1910.14276"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_60_1","volume-title":"Computing Maximum Flow with Augmenting Electrical Flows. In 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2016","author":"M\u0105dry Aleksander","year":"2016","unstructured":"Aleksander M\u0105dry . 2016 . Computing Maximum Flow with Augmenting Electrical Flows. In 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2016 , 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. IEEE Computer Society, 593\u2013602. Available at arxiv:1608.06016 Aleksander M\u0105dry. 2016. Computing Maximum Flow with Augmenting Electrical Flows. In 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. IEEE Computer Society, 593\u2013602. Available at arxiv:1608.06016"},{"key":"e_1_3_2_1_61_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. 2019\u20132036","author":"Madry Aleksander","year":"2014","unstructured":"Aleksander Madry , Damian Straszak , and Jakub Tarnawski . 2014 . Fast generation of random spanning trees and the effective resistance metric . In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. 2019\u20132036 . Aleksander Madry, Damian Straszak, and Jakub Tarnawski. 2014. Fast generation of random spanning trees and the effective resistance metric. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. 2019\u20132036."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_3_2_1_64_1","volume-title":"Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Nanongkai Danupon","year":"2017","unstructured":"Danupon Nanongkai , Thatchaphol Saranurak , and Christian Wulff-Nilsen . 2017 . Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , Berkeley, CA, USA , October 15-17, 2017. IEEE Computer Society, 950\u2013961. Available at arxiv:1708.03962 Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. 2017. Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. IEEE Computer Society, 950\u2013961. Available at arxiv:1708.03962"},{"key":"e_1_3_2_1_65_1","unstructured":"Jelani Nelson and Huacheng Yu. 2020. Optimal bounds for approximate counting. arXiv preprint arXiv:2010.02116.  Jelani Nelson and Huacheng Yu. 2020. Optimal bounds for approximate counting. arXiv preprint arXiv:2010.02116."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch130"},{"key":"e_1_3_2_1_67_1","first-page":"1","article-title":"A polynomial-time algorithm, based on Newton\u2019s method, for linear programming","volume":"40","author":"Renegar James","year":"1988","unstructured":"James Renegar . 1988 . A polynomial-time algorithm, based on Newton\u2019s method, for linear programming . Mathematical Programming , 40 , 1 - 3 (1988), 59\u201393. James Renegar. 1988. A polynomial-time algorithm, based on Newton\u2019s method, for linear programming. Mathematical Programming, 40, 1-3 (1988), 59\u201393.","journal-title":"Mathematical Programming"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.162"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188852"},{"key":"e_1_3_2_1_70_1","volume-title":"Nearly Maximum Flows in Nearly Linear Time. In 54th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2013","author":"Sherman Jonah","year":"2013","unstructured":"Jonah Sherman . 2013 . Nearly Maximum Flows in Nearly Linear Time. In 54th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2013 , Berkeley, CA, USA , October 26-29, 2013. 263\u2013269. Available at arxiv:1304.2077 Jonah Sherman. 2013. Nearly Maximum Flows in Nearly Linear Time. In 54th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, October 26-29, 2013. 263\u2013269. Available at arxiv:1304.2077"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055501"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00091"},{"key":"e_1_3_2_1_73_1","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC 2004","author":"Daniel","year":"2004","unstructured":"Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems . In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC 2004 , Chicago, IL, USA , June 13-16, 2004 . 81\u201390. Available at arxiv:0809.3232 Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC 2004, Chicago, IL, USA, June 13-16, 2004. 81\u201390. Available at arxiv:0809.3232"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520068","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":75,"alternative-id":["10.1145\/3519935.3520068","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520068","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}