{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T16:16:54Z","timestamp":1772468214249,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":99,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1844855,CCF-1955039,CCF-1749609,CCF-1740551,DMS-1839116,DMS-2023166,CCF-1718533"],"award-info":[{"award-number":["CCF-1844855,CCF-1955039,CCF-1749609,CCF-1740551,DMS-1839116,DMS-2023166,CCF-1718533"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["715672"],"award-info":[{"award-number":["715672"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451108","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"859-869","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Minimum cost flows, MDPs, and \u2113\n            <sub>1<\/sub>\n            -regression in nearly linear time for dense instances"],"prefix":"10.1145","author":[{"given":"Jan","family":"van den Brand","sequence":"first","affiliation":[{"name":"KTH, Sweden"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, USA \/ Microsoft Research, USA"}]},{"given":"Yang P.","family":"Liu","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8386-7168","authenticated-orcid":false,"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"Princeton University, USA \/ Institute for Advanced Study at Princeton, USA"}]},{"given":"Di","family":"Wang","sequence":"additional","affiliation":[{"name":"Google Research, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Yang","author":"Agarwal Alekh","year":"2020","unstructured":"Alekh Agarwal, Sham M. Kakade, and Lin F. Yang. 2020. Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal. In COLT (Proceedings of Machine Learning Research, Vol. 125). PMLR, 67\u201383."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Josh Alman and Virginia Vassilevska Williams. 2021. A Refined Laser Method and Faster Matrix Multiplication. In SODA. https:\/\/arxiv.org\/pdf\/2010.05846.pdf.","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems","author":"Auer Peter","year":"2006","unstructured":"Peter Auer and Ronald Ortner. 2006. Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning. In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, Bernhard Sch\u00f6lkopf, John C. Platt, and Thomas Hofmann (Eds.). MIT Press, 49\u201356. http:\/\/papers.nips.cc\/paper\/3052-logarithmic-online-regret-bounds-for-undiscounted-reinforcement-learning"},{"key":"e_1_3_2_1_5_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."},{"key":"e_1_3_2_1_6_1","volume-title":"Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning 91, 3","author":"Azar Mohammad Gheshlaghi","year":"2013","unstructured":"Mohammad Gheshlaghi Azar, R\u00e9mi Munos, and Hilbert J Kappen. 2013. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning 91, 3 (2013), 325\u2013349."},{"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). https:\/\/arxiv.org\/pdf\/2004.08432."},{"key":"e_1_3_2_1_8_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."},{"key":"e_1_3_2_1_9_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."},{"key":"e_1_3_2_1_10_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 L1-Regression in Nearly Linear Time for Dense Instances. CoRR abs\/2101.05719 (2021)."},{"key":"e_1_3_2_1_11_1","volume-title":"Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.","author":"van den Brand Jan","year":"2020","unstructured":"Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. 2020. Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. In FOCS. IEEE, 919\u2013930."},{"key":"e_1_3_2_1_12_1","volume-title":"Aaron Sidford, and Zhao Song.","author":"van den Brand Jan","year":"2020","unstructured":"Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. 2020. Solving tall dense linear programs in nearly linear time. In STOC. ACM, 775\u2013788. https:\/\/arxiv.org\/pdf\/2002.02304.pdf."},{"key":"e_1_3_2_1_13_1","volume-title":"Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds","author":"van den Brand Jan","unstructured":"Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. 2019. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. In FOCS. IEEE Computer Society, 456\u2013480."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422469"},{"key":"e_1_3_2_1_15_1","unstructured":"Kenneth L Clarkson. 2005. Subgradient and sampling algorithms for l 1 regression. In SODA. 257\u2013266."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/140963698"},{"key":"e_1_3_2_1_17_1","volume-title":"Woodruff","author":"Clarkson Kenneth L.","year":"2013","unstructured":"Kenneth L. Clarkson and David P. Woodruff. 2013. Low rank approximation and regression in input sparsity time. In STOC. ACM, 81\u201390."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1474-6670(17)42067-2"},{"key":"e_1_3_2_1_19_1","volume-title":"1st Symposium on Simplicity in Algorithms (SOSA). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Cohen Michael B","year":"2018","unstructured":"Michael B Cohen, TS Jayram, and Jelani Nelson. 2018. Simple analyses of the sparse Johnson-Lindenstrauss transform. In 1st Symposium on Simplicity in Algorithms (SOSA). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC). 343\u2013352","author":"Cohen Michael B.","year":"2014","unstructured":"Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. 2014. Solving sdd linear systems in nearly $m\u0142og^1\/2n$ time. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC). 343\u2013352."},{"key":"e_1_3_2_1_21_1","volume-title":"Yin Tat Lee, and Zhao Song","author":"Cohen Michael B.","year":"2019","unstructured":"Michael B. Cohen, Yin Tat Lee, and Zhao Song. 2019. Solving linear programs in the current matrix multiplication time. In STOC. ACM, 938\u2013942. https:\/\/arxiv.org\/pdf\/1810.07896."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039734"},{"key":"e_1_3_2_1_23_1","volume-title":"Cohen and Richard Peng","author":"Michael","year":"2015","unstructured":"Michael B. Cohen and Richard Peng. 2015. $\\ell_p$ Row Sampling by Lewis Weights. In STOC. ACM, 183\u2013192."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384326"},{"key":"e_1_3_2_1_25_1","volume-title":"V\u00e9gh","author":"Dadush Daniel","year":"2020","unstructured":"Daniel Dadush, Bento Natura, and L\u00e1szl\u00f3 A. V\u00e9gh. 2020. Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers. CoRR abs\/2009.04942 (2020). arxiv:2009.04942 https:\/\/arxiv.org\/abs\/2009.04942"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.728912"},{"key":"e_1_3_2_1_28_1","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic Efim A","year":"1970","unstructured":"Efim A Dinic. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. In Soviet Math. Doklady, Vol. 11. 1277\u20131280.","journal-title":"Soviet Math. Doklady"},{"key":"e_1_3_2_1_29_1","volume-title":"Conference On Learning Theory, COLT 2018","author":"Durfee David","year":"2018","unstructured":"David Durfee, Kevin A. Lai, and Saurabh Sawlani. 2018. $\\ell_1$ Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018 (Proceedings of Machine Learning Research, Vol. 75), S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.). PMLR, 1626\u20131656. http:\/\/proceedings.mlr.press\/v75\/durfee18a.html"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/42282.214090"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Fran\u00e7ois Le Gall. 2014. Powers of tensors and fast matrix multiplication. In ISSAC. ACM 296\u2013303.","DOI":"10.1145\/2608628.2608664"},{"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":"The Expander Hierarchy and its Applications to Dynamic Graph Algorithms. CoRR abs\/2005.02369","author":"Goranci Gramoz","year":"2020","unstructured":"Gramoz Goranci, Harald R\u00e4cke, Thatchaphol Saranurak, and Zihan Tan. 2020. The Expander Hierarchy and its Applications to Dynamic Graph Algorithms. CoRR abs\/2005.02369 (2020). arxiv:2005.02369 https:\/\/arxiv.org\/abs\/2005.02369"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859902"},{"key":"e_1_3_2_1_37_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 https:\/\/arxiv.org\/abs\/2004.07470"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559902"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993735"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_3_2_1_42_1","unstructured":"Tarun Kathuria. 2020. A Potential Reduction Inspired Algorithm for Exact Max Flow in Almost O(m\\^4\/3) Time. In FOCS. https:\/\/arxiv.org\/pdf\/2009.03260.pdf."},{"key":"e_1_3_2_1_43_1","volume-title":"Singh","author":"Kearns Michael J.","year":"1998","unstructured":"Michael J. Kearns and Satinder P. Singh. 1998. Finite-Sample Convergence Rates for Q-Learning and Indirect Algorithms. In Advances in Neural Information Processing Systems 11, [NIPS Conference, Denver, Colorado, USA, November 30 - December 5, 1998], Michael J. Kearns, Sara A. Solla, and David A. Cohn (Eds.). The MIT Press, 996\u20131002. http:\/\/papers.nips.cc\/paper\/1531-finite-sample-convergence-rates-for-q-learning-and-indirect-algorithms"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_47_1","volume-title":"STOC'16: Proceedings of the 48th Annual ACM Symposium on Theory of Computing.","author":"Kyng Rasmus","unstructured":"Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. 2016. Sparsified cholesky and multigrid solvers for connection laplacians. In STOC'16: Proceedings of the 48th Annual ACM Symposium on Theory of Computing."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.16"},{"key":"e_1_3_2_1_50_1","volume-title":"Spielman","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee, Richard Peng, and Daniel A. Spielman. 2015. Sparsified Cholesky Solvers for SDD linear systems. CoRR abs\/1506.08204 (2015)."},{"key":"e_1_3_2_1_51_1","volume-title":"55th Annual IEEE Symposium on Foundations of Computer Science (FOCS). https:\/\/arxiv.org\/pdf\/1312","author":"Lee Yin Tat","year":"2014","unstructured":"Yin Tat Lee and Aaron Sidford. 2014. Path finding methods for linear programming: Solving linear programs in $O( \\sqrtrank )$ iterations and faster algorithms for maximum flow. In 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS). https:\/\/arxiv.org\/pdf\/1312.6677.pdf, https:\/\/arxiv.org\/pdf\/1312.6713.pdf, 424\u2013433."},{"key":"e_1_3_2_1_52_1","volume-title":"Efficient Inverse Maintenance and Faster Algorithms for Linear Programming","author":"Lee Yin Tat","unstructured":"Yin Tat Lee and Aaron Sidford. 2015. Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In FOCS. IEEE Computer Society, 230\u2013249."},{"key":"e_1_3_2_1_53_1","unstructured":"Yin Tat Lee and Aaron Sidford. 2019. Solving Linear Programs with $\\sqrtrank$ Linear System Solves. In arXiv preprint. https:\/\/arxiv.org\/pdf\/1910.08033.pdf."},{"key":"e_1_3_2_1_54_1","volume-title":"COLT (Proceedings of Machine Learning Research","volume":"2157","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 COLT (Proceedings of Machine Learning Research, Vol. 99). PMLR, 2140\u20132157. https:\/\/arxiv.org\/pdf\/1905.04447."},{"key":"e_1_3_2_1_55_1","volume-title":"Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model. CoRR abs\/2005.12900","author":"Li Gen","year":"2020","unstructured":"Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. 2020. Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model. CoRR abs\/2005.12900 (2020). arxiv:2005.12900 https:\/\/arxiv.org\/abs\/2005.12900"},{"key":"e_1_3_2_1_56_1","volume-title":"On the Complexity of Solving Markov Decision Problems. In UAI '95: Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence","author":"Littman Michael L.","year":"1995","unstructured":"Michael L. Littman, Thomas L. Dean, and Leslie Pack Kaelbling. 1995. On the Complexity of Solving Markov Decision Problems. In UAI '95: Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence, Montreal, Quebec, Canada, August 18-20, 1995. 394\u2013402. https:\/\/dslpitt.org\/uai\/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=457&proceeding_id=11"},{"key":"e_1_3_2_1_57_1","volume-title":"Breaking the n-Pass Barrier: A Streaming Algorithm for Maximum Weight Bipartite Matching. CoRR abs\/2009.06106","author":"Liu S. Cliff","year":"2020","unstructured":"S. Cliff Liu, Zhao Song, and Hengjie Zhang. 2020. Breaking the n-Pass Barrier: A Streaming Algorithm for Maximum Weight Bipartite Matching. CoRR abs\/2009.06106 (2020)."},{"key":"e_1_3_2_1_58_1","unstructured":"Yang P Liu and Aaron Sidford. 2020. Faster Divergence Maximization for Faster Maximum Flow. In FOCS. https:\/\/arxiv.org\/pdf\/2003.08929.pdf."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Yang P Liu and Aaron Sidford. 2020. Faster Energy Maximization for Faster Maximum Flow. In STOC. https:\/\/arxiv.org\/pdf\/1910.14276.pdf.","DOI":"10.1145\/3357713.3384247"},{"key":"e_1_3_2_1_60_1","unstructured":"Omid Madani. 2002. Polynomial Value Iteration Algorithms for Detrerminstic MDPs. In UAI. 311\u2013318."},{"key":"e_1_3_2_1_61_1","volume-title":"Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back","author":"Madry Aleksander","unstructured":"Aleksander Madry. 2013. Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back. In FOCS. IEEE Computer Society, 253\u2013262."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018064306595"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401388926"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402416803"},{"key":"e_1_3_2_1_66_1","volume-title":"Stronger l\\(_\\mbox2\\)\/l\\(_\\mbox2\\) compressed sensing","author":"Nakos Vasileios","unstructured":"Vasileios Nakos and Zhao Song. 2019. Stronger l\\(_\\mbox2\\)\/l\\(_\\mbox2\\) compressed sensing; without iterating. In STOC. ACM, 289\u2013297."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Vasileios Nakos Zhao Song and Zhengyu Wang. 2019. (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless. In FOCS. IEEE Computer Society 1568\u20131577.","DOI":"10.1109\/FOCS.2019.00092"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0348"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801033"},{"key":"e_1_3_2_1_72_1","unstructured":"James B Orlin. 1984. Genuinely polynomial simplex and non-simplex algorithms for the minimum cost flow problem. (1984)."},{"key":"e_1_3_2_1_73_1","volume-title":"A faster strongly polynomial minimum cost flow algorithm. Operations research 41, 2","author":"Orlin James B","year":"1993","unstructured":"James B Orlin. 1993. A faster strongly polynomial minimum cost flow algorithm. Operations research 41, 2 (1993), 338\u2013350."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2493252.2493254"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591832"},{"key":"e_1_3_2_1_76_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Price Eric","year":"2017","unstructured":"Eric Price, Zhao Song, and David P Woodruff. 2017. Fast Regression with an $ ell_infty $ Guarantee. In 44th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_77_1","first-page":"1","article-title":"A polynomial-time algorithm, based on Newton's method, for linear programming","volume":"40","author":"Renegar James","year":"1988","unstructured":"James Renegar. 1988. A polynomial-time algorithm, based on Newton's method, for linear programming. Math. Program. 40, 1-3 (1988), 59\u201393.","journal-title":"Math. Program."},{"key":"e_1_3_2_1_78_1","volume-title":"Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract)","author":"Sankowski Piotr","unstructured":"Piotr Sankowski. 2004. Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). In FOCS. IEEE Computer Society, 509\u2013517."},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.162"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2015.0753"},{"key":"e_1_3_2_1_81_1","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Sidford Aaron","year":"2018","unstructured":"Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. 2018. Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montr\u00e9al, Canada. 5192\u20135202."},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.50"},{"key":"e_1_3_2_1_83_1","volume-title":"Woodruff","author":"Sohler Christian","year":"2011","unstructured":"Christian Sohler and David P. Woodruff. 2011. Subspace embeddings for the L\\(_\\mbox1\\)-norm with applications. In STOC. ACM, 755\u2013764."},{"key":"e_1_3_2_1_84_1","unstructured":"Zhao Song and Zheng Yu. 2020. Oblivious Sketching-based Central Path Method for Solving Linear Programming Problems. In manuscript. https:\/\/openreview.net\/forum?id=fGiKxvF-eub."},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_86_1","volume-title":"Spielman and Shang-Hua Teng","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 STOC. ACM, 81\u201390."},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579369"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90022-W"},{"key":"e_1_3_2_1_89_1","volume-title":"Speeding-Up Linear Programming Using Fast Matrix Multiplication (Extended Abstract)","author":"Vaidya Pravin M.","unstructured":"Pravin M. Vaidya. 1989. Speeding-Up Linear Programming Using Fast Matrix Multiplication (Extended Abstract). In FOCS. IEEE Computer Society, 332\u2013337."},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592148"},{"key":"e_1_3_2_1_91_1","volume-title":"Variance-reduced Q-learning is minimax optimal. CoRR abs\/1906.04697","author":"Wainwright Martin J.","year":"2019","unstructured":"Martin J. Wainwright. 2019. Variance-reduced Q-learning is minimax optimal. CoRR abs\/1906.04697 (2019). arxiv:1906.04697 http:\/\/arxiv.org\/abs\/1906.04697"},{"key":"e_1_3_2_1_92_1","volume-title":"Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear Running Time. CoRR abs\/1704.01869","author":"Wang Mengdi","year":"2017","unstructured":"Mengdi Wang. 2017. Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear Running Time. CoRR abs\/1704.01869 (2017). arxiv:1704.01869 http:\/\/arxiv.org\/abs\/1704.01869"},{"key":"e_1_3_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2019.1000"},{"key":"e_1_3_2_1_94_1","volume-title":"Woodruff","author":"Wang Ruosong","year":"2019","unstructured":"Ruosong Wang and David P. Woodruff. 2019. Tight Bounds for Lp Oblivious Subspace Embeddings. In SODA. SIAM, 1825\u20131843."},{"key":"e_1_3_2_1_95_1","doi-asserted-by":"crossref","unstructured":"Virginia Vassilevska Williams. 2012. Multiplying matrices faster than coppersmith-winograd. In STOC. ACM 887\u2013898.","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_1_96_1","volume-title":"COLT (JMLR Workshop and Conference Proceedings","volume":"567","author":"David","unstructured":"David P. Woodruff and Qin Zhang. 2013. Subspace Embeddings and (ell_p)-Regression Using Exponential Random Variables. In COLT (JMLR Workshop and Conference Proceedings, Vol. 30). JMLR.org, 546\u2013567."},{"key":"e_1_3_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch41"},{"key":"e_1_3_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0149"},{"key":"e_1_3_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0516"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451108","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":99,"alternative-id":["10.1145\/3406325.3451108","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451108","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}