{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T19:26:42Z","timestamp":1793129202028,"version":"4.5.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-2006464, HDR TRIPODS award 2216899, CCF-1934876, CCF-2008305"],"award-info":[{"award-number":["CCF-2006464, HDR TRIPODS award 2216899, CCF-1934876, CCF-2008305"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649725","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"83-94","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Maximum Bipartite Matching in \ud835\udc5b\n            <sup>2+\ud835\udc5c(1)<\/sup>\n            Time via a Combinatorial Algorithm"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7839-751X","authenticated-orcid":false,"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Toyota Technological Institute, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2601-1689","authenticated-orcid":false,"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585240"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Amir Abboud Karl Bringmann Seri Khoury and Or Zamir. 2022. Hardness of Approximation in P via Short Cycle Removal: Cycle Detection Distance Oracles and Beyond. arXiv preprint arXiv:2204.10465.","DOI":"10.1145\/3519935.3520066"},{"key":"e_1_3_2_1_3_1","volume-title":"Throughput-Competitive On-Line Routing. In 34th Annual Symposium on Foundations of Computer Science","author":"Awerbuch Baruch","year":"1993","unstructured":"Baruch Awerbuch, Yossi Azar, and Serge A. Plotkin. 1993. Throughput-Competitive On-Line Routing. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993. 32\u201340."},{"key":"e_1_3_2_1_4_1","volume-title":"Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020","author":"Axiotis Kyriakos","year":"2020","unstructured":"Kyriakos Axiotis, Aleksander Madry, and Adrian Vladu. 2020. Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. 93\u2013104."},{"key":"e_1_3_2_1_5_1","volume-title":"Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. In LIPIcs-Leibniz International Proceedings in Informatics. 80","author":"Bernstein Aaron","year":"2017","unstructured":"Aaron Bernstein. 2017. Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. In LIPIcs-Leibniz International Proceedings in Informatics. 80."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00108"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00107"},{"key":"e_1_3_2_1_8_1","volume-title":"Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022","author":"Chen Li","year":"2022","unstructured":"Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2022. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022. 612\u2013623."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.79"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039734"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"Samuel","year":"2008","unstructured":"Samuel I. Daitch and Daniel A. Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, Cynthia Dwork (Ed.). ACM, 451\u2013460."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1555"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743463"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806697"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0505-z"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.155"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90142-3"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488704"},{"key":"e_1_3_2_1_24_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)."},{"key":"e_1_3_2_1_25_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. 803\u2013814."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806708"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_28_1","volume-title":"Computing Maximum Flow with Augmenting Electrical Flows. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016","author":"Madry Aleksander","year":"2016","unstructured":"Aleksander Madry. 2016. Computing Maximum Flow with Augmenting Electrical Flows. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. 593\u2013602."},{"key":"e_1_3_2_1_29_1","volume-title":"21st Annual Symposium on Foundations of Computer Science","author":"Micali Silvio","year":"1980","unstructured":"Silvio Micali and Vijay V. Vazirani. 1980. An O(sqrt(\u011brt v\u011brt ) \u011brt E\u011brt ) Algorithm for Finding Maximum Matching in General Graphs. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980. IEEE Computer Society, 17\u201327."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"e_1_3_2_1_32_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer."},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","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, Chicago, IL, USA, June 13-16, 2004. 81\u201390."},{"key":"e_1_3_2_1_34_1","volume-title":"64th IEEE Annual Symposium on Foundations of Computer Science (FOCS), (to appear).","author":"van den Brand Jan","year":"2023","unstructured":"Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. 2023. A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. In 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS), (to appear)."},{"key":"e_1_3_2_1_35_1","volume-title":"Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020","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 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. 919\u2013930."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305952"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649725","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":36,"alternative-id":["10.1145\/3618260.3649725","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649725","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}