{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:01:33Z","timestamp":1772906493529,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":50,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316303","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"938-942","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["Solving linear programs in the current matrix multiplication time"],"prefix":"10.1145","author":[{"given":"Michael B.","family":"Cohen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, USA \/ Microsoft Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"University of Washington, USA \/ University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746554"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00061"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188776"},{"key":"e_1_3_2_1_4_1","first-page":"909","volume-title":"2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Cohen CKK","unstructured":"{ CKK + 18} Michael B Cohen , Jonathan Kelner , Rasmus Kyng , John Peebles , Richard Peng , Anup B Rao , and Aaron Sidford . Solving directed laplacian systems in nearly-linear time through sparse LU factorizations . In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 898\u2013 909 . IEEE, 2018. {CKK + 18} Michael B Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B Rao, and Aaron Sidford. Solving directed laplacian systems in nearly-linear time through sparse LU factorizations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 898\u2013909. IEEE, 2018."},{"key":"e_1_3_2_1_5_1","first-page":"282","volume-title":"Proceedings of the forty-third annual ACM symposium on Theory of computing","author":"Paul Christiano CKM","unstructured":"{ CKM + 11} Paul Christiano , Jonathan A Kelner , Aleksander Madry , Daniel A Spielman , and Shang-Hua Teng . Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs . In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 273\u2013 282 . ACM, 2011. {CKM + 11} Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 273\u2013282. ACM, 2011."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_1_7_1","volume-title":"Las vegas algorithms for linear and integer programming when the dimension is small. Journal of the ACM ( JACM), 42(2):488\u2013499","author":"Current Matrix Multiplication Solving Linear","year":"1995","unstructured":"Solving Linear Programs in the Current Matrix Multiplication Time STOC \u201919, June 23\u201326, 2019, Phoenix, AZ, USA {Cla95} Kenneth L Clarkson . Las vegas algorithms for linear and integer programming when the dimension is small. Journal of the ACM ( JACM), 42(2):488\u2013499 , 1995 . Solving Linear Programs in the Current Matrix Multiplication Time STOC \u201919, June 23\u201326, 2019, Phoenix, AZ, USA {Cla95} Kenneth L Clarkson. Las vegas algorithms for linear and integer programming when the dimension is small. Journal of the ACM ( JACM), 42(2):488\u2013499, 1995."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897647"},{"key":"e_1_3_2_1_9_1","volume-title":"Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In arXiv preprint. https:\/\/arxiv. org\/pdf\/1810.07896","author":"Cohen Michael B.","year":"2018","unstructured":"{CLS18} Michael B. Cohen , Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In arXiv preprint. https:\/\/arxiv. org\/pdf\/1810.07896 , 2018 . {CLS18} Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In arXiv preprint. https:\/\/arxiv. org\/pdf\/1810.07896, 2018."},{"key":"e_1_3_2_1_10_1","first-page":"771","volume-title":"Proceedings of the Twenty-Eighth Annual ACMSIAM Symposium on Discrete Algorithms(SODA)","author":"Cohen Michael B","unstructured":"{CMSV17} Michael B Cohen , Aleksander M\u0105dry , Piotr Sankowski , and Adrian Vladu . Negative-weight shortest paths and unit capacity minimum cost flow in H O (m 10 \/7 log W ) time . In Proceedings of the Twenty-Eighth Annual ACMSIAM Symposium on Discrete Algorithms(SODA) , pages 752\u2013 771 . SIAM, 2017. {CMSV17} Michael B Cohen, Aleksander M\u0105dry, Piotr Sankowski, and Adrian Vladu. Negative-weight shortest paths and unit capacity minimum cost flow in H O (m 10 \/7 log W ) time. In Proceedings of the Twenty-Eighth Annual ACMSIAM Symposium on Discrete Algorithms(SODA), pages 752\u2013771. SIAM, 2017."},{"key":"e_1_3_2_1_11_1","first-page":"913","volume-title":"Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on","author":"Cohen Michael B","unstructured":"{CMTV17} Michael B Cohen , Aleksander Madry , Dimitris Tsipras , and Adrian Vladu . Matrix scaling and balancing via box constrained newton\u2019s method and interior point methods . In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on , pages 902\u2013 913 . IEEE, 2017. {CMTV17} Michael B Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton\u2019s method and interior point methods. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 902\u2013913. IEEE, 2017."},{"key":"e_1_3_2_1_12_1","first-page":"6","volume-title":"Proceedings of the nineteenth annual ACM symposium on Theory of computing(STOC)","author":"Coppersmith Don","unstructured":"{CW87} Don Coppersmith and Shmuel Winograd . Matrix multiplication via arithmetic progressions . In Proceedings of the nineteenth annual ACM symposium on Theory of computing(STOC) , pages 1\u2013 6 . ACM, 1987. {CW87} Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proceedings of the nineteenth annual ACM symposium on Theory of computing(STOC), pages 1\u20136. ACM, 1987."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0308210511001648"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188960"},{"key":"e_1_3_2_1_21_1","first-page":"582","volume-title":"2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Kyng Rasmus","unstructured":"{KS16} Rasmus Kyng and Sushant Sachdeva . Approximate gaussian elimination for laplacians-fast, sparse, and simple . In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 573\u2013 582 . IEEE, 2016. {KS16} Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians-fast, sparse, and simple. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 573\u2013582. IEEE, 2016."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_23_1","first-page":"1046","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA)","author":"Gall Francois Le","unstructured":"{LGU18} Francois Le Gall and Florent Urrutia . Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor . In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA) , pages 1029\u2013 1046 . SIAM, 2018. {LGU18} Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA), pages 1029\u20131046. SIAM, 2018."},{"key":"e_1_3_2_1_24_1","volume-title":"Path finding I: Solving linear programs with H O ( \u221a r ank ) linear system solves. arXiv preprint arXiv:1312.6677","author":"Lee Yin Tat","year":"2013","unstructured":"{LS13} Yin Tat Lee and Aaron Sidford . Path finding I: Solving linear programs with H O ( \u221a r ank ) linear system solves. arXiv preprint arXiv:1312.6677 , 2013 . {LS13} Yin Tat Lee and Aaron Sidford. Path finding I: Solving linear programs with H O ( \u221a r ank ) linear system solves. arXiv preprint arXiv:1312.6677, 2013."},{"key":"e_1_3_2_1_25_1","first-page":"433","volume-title":"2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Lee Yin Tat","unstructured":"{LS14} Yin Tat Lee and Aaron Sidford . Path finding methods for linear programming: Solving linear programs in O ( \u221a r ank ) iterations and faster algorithms for maximum flow . In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) , pages 424\u2013 433 . IEEE, 2014. {LS14} Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in O ( \u221a r ank ) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 424\u2013433. IEEE, 2014."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.23"},{"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","first-page":"602","volume-title":"2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Madry Aleksander","unstructured":"{Mad16} Aleksander Madry . Computing maximum flow with augmenting electrical flows . In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 593\u2013 602 . IEEE, 2016. {Mad16} Aleksander Madry. Computing maximum flow with augmenting electrical flows. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 593\u2013602. IEEE, 2016."},{"key":"e_1_3_2_1_29_1","volume-title":"Progress in Mathematical Programming: Interior-Point and Related Methods","author":"Megiddo Nimrod","year":"2012","unstructured":"{Meg12} Nimrod Megiddo . Progress in Mathematical Programming: Interior-Point and Related Methods . Springer Science & amp; Business Media, 2012 . {Meg12} Nimrod Megiddo. Progress in Mathematical Programming: Interior-Point and Related Methods. Springer Science & Business Media, 2012."},{"key":"e_1_3_2_1_30_1","volume-title":"Self-concordant functions and polynomial-time methods in convex programming. Report","author":"Nesterov Yu","year":"1989","unstructured":"{NN89} Yu Nesterov and Arkadi Nemirovsky . Self-concordant functions and polynomial-time methods in convex programming. Report , Central Economic and Mathematic Institute , USSR Acad. Sci, 1989 . {NN89} Yu Nesterov and Arkadi Nemirovsky. Self-concordant functions and polynomial-time methods in convex programming. Report, Central Economic and Mathematic Institute, USSR Acad. Sci, 1989."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801033"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-point polynomial algorithms in convex programming","author":"Nesterov Yurii","year":"1994","unstructured":"{NN94} Yurii Nesterov and Arkadii Nemirovskii . Interior-point polynomial algorithms in convex programming , volume 13 . Siam , 1994 . {NN94} Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming, volume 13. Siam, 1994."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070200296"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2794549.3114257"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718812","volume-title":"A mathematical view of interior-point methods in convex optimization","author":"Renegar James","year":"2001","unstructured":"{Ren01} James Renegar . A mathematical view of interior-point methods in convex optimization , volume 3 . Siam , 2001 . {Ren01} James Renegar. A mathematical view of interior-point methods in convex optimization, volume 3. Siam, 2001."},{"key":"e_1_3_2_1_37_1","volume-title":"Interior point methods for linear optimization","author":"Roos Cornelis","year":"2005","unstructured":"{RTV05} Cornelis Roos , Tam\u00e1s Terlaky , and J- Ph Vial . Interior point methods for linear optimization . Springer Science & amp; Business Media, 2005 . {RTV05} Cornelis Roos, Tam\u00e1s Terlaky, and J-Ph Vial. Interior point methods for linear optimization. Springer Science & Business Media, 2005."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_41_1","volume-title":"Interior point methods of mathematical programming","author":"Terlaky Tam\u00e1s","year":"2013","unstructured":"{Ter13} Tam\u00e1s Terlaky . Interior point methods of mathematical programming , volume 5 . Springer Science & amp; Business Media, 2013 . {Ter13} Tam\u00e1s Terlaky. Interior point methods of mathematical programming, volume 5. Springer Science & Business Media, 2013."},{"key":"e_1_3_2_1_42_1","volume-title":"An algorithm for linear programming which requires O (((m + n)n 2 + (m + n) 1 .5 n)L)arithmetic operations","author":"Vaidya Pravin M","year":"1987","unstructured":"{Vai87} Pravin M Vaidya . An algorithm for linear programming which requires O (((m + n)n 2 + (m + n) 1 .5 n)L)arithmetic operations . In FOCS. IEEE , 1987 . {Vai87} Pravin M Vaidya. An algorithm for linear programming which requires O (((m + n)n 2 + (m + n) 1 .5 n)L)arithmetic operations. In FOCS. IEEE, 1987."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63500"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"issue":"106","key":"e_1_3_2_1_46_1","first-page":"336","article-title":"Inverting modified matrices","volume":"42","author":"Woodbury Max A","year":"1950","unstructured":"{Woo50} Max A Woodbury . Inverting modified matrices . Memorandum report , 42 ( 106 ): 336 , 1950 . {Woo50} Max A Woodbury. Inverting modified matrices. Memorandum report, 42(106):336, 1950.","journal-title":"Memorandum report"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611971453","volume-title":"Primal-dual interior-point methods","author":"Wright Stephen J","year":"1997","unstructured":"{Wri97} Stephen J Wright . Primal-dual interior-point methods , volume 54 . Siam , 1997 . {Wri97} Stephen J Wright. Primal-dual interior-point methods, volume 54. Siam, 1997."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/265937"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.1.53"},{"key":"e_1_3_2_1_50_1","unstructured":"Abstract 1 Introduction 1.1 Related Work 2 Results and Techniques 2.1 Central Path Method 2.2 Projection Maintenance via Lazy Update 3 Notations References  Abstract 1 Introduction 1.1 Related Work 2 Results and Techniques 2.1 Central Path Method 2.2 Projection Maintenance via Lazy Update 3 Notations References"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3316303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:00Z","timestamp":1750204440000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":50,"alternative-id":["10.1145\/3313276.3316303","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316303","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"}}]}}