Fetching the paper…
Reading the bibliography…
This paper shows how to solve linear programs of the form $\min_{Ax=b,x\geq0} c^\top x$ with $n$ variables in time $$O^*((n^{\omega}+n^{2.5-\alpha/2}+n^{2+1/6}) \log(n/\delta))$$ where $\omega$ is the exponent of matrix multiplication, $\alpha$ is the dual exponent of matrix multiplication, and $\delta$ is the relative accuracy.
Inverting modified matrices
Max A Woodbury · 1950
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
Earlier work this paper cites.
How to multiply matrices faster
Victor Pan · 1984
Earlier work this paper cites.
Matrix multiplication via arithmetic progressions
Don Coppersmith and Shmuel Winograd · 1987
Earlier work this paper cites.
A polynomial-time algorithm, based on newton’s method, for linear programming
James Renegar · 1988
Earlier work this paper cites.
Self-concordant functions and polynomial-time methods in convex programming
Yu Nesterov and Arkadi Nemirovsky · 1989
Earlier work this paper cites.
A new algorithm for minimizing convex functions over convex sets
Pravin M Vaidya · 1989
Earlier work this paper cites.
Speeding-up linear programming using fast matrix multiplication
Pravin M Vaidya · 1989
Earlier work this paper cites.
Acceleration and parallelization of the path-following interior point method for a linearly constrained convex quadratic problem
Yu Nesterov and Arkadi Nemirovsky · 1991
Earlier work this paper cites.
Interior-point polynomial algorithms in convex programming
Yurii Nesterov and Arkadii Nemirovskii · 1994
Earlier work this paper cites.
An O ( n L ) {O}(\sqrt{nL}) -iteration homogeneous and self-dual linear programming algorithm
Yinyu Ye, Michael J Todd, and Shinji Mizuno · 1994
Earlier work this paper cites.
Primal-dual interior-point methods
Stephen J Wright · 1997
Earlier work this paper cites.
Interior point algorithms: theory and analysis
Yinyu Ye · 1997
Earlier work this paper cites.
A mathematical view of interior-point methods in convex optimization
James Renegar · 2001
Earlier work this paper cites.
Self-regular functions and new search directions for linear and semidefinite optimization
Jiming Peng, Cornelis Roos, and Tamás Terlaky · 2002
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
Interior point methods for linear optimization
Cornelis Roos, Tamás Terlaky, and J-Ph Vial · 2005
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Earlier work this paper cites.
Approaching optimality for solving sdd linear systems
Ioannis Koutis, Gary L Miller, and Richard Peng · 2010
Earlier work this paper cites.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng · 2011
Earlier work this paper cites.
A nearly-m log n time solver for sdd linear systems
Ioannis Koutis, Gary L Miller, and Richard Peng · 2011
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Progress in Mathematical Programming: Interior-Point and Related Methods
Nimrod Megiddo · 2012
Cited alongside, same era.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Cited alongside, same era.
Low rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2013
Cited alongside, same era.
Improved bound for complexity of matrix multiplication
Alexander Munro Davie and Andrew James Stothers · 2013
Cited alongside, same era.
A simple, combinatorial algorithm for solving sdd systems in nearly-linear time
Negative-weight shortest paths and unit capacity minimum cost flow in O ~ ( m 10 / 7 log W ) \widetilde{{O}}(m^{10/7}\log{W}) time
Michael B Cohen, Aleksander Mądry, Piotr Sankowski, and Adrian Vladu · 2017
Later among the works it cites.
Matrix scaling and balancing via box constrained newton’s method and interior point methods
Michael B Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu · 2017
Later among the works it cites.
Faster online matrix-vector multiplication
Kasper Green Larsen and Ryan Williams · 2017
Later among the works it cites.
Limits on all known (and some unknown) approaches to matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2018
Closest in time.
An homotopy method for ℓ p \ell_{p} regression provably beyond self-concordance and in input-sparsity time
Sébastien Bubeck, Michael B Cohen, Yin Tat Lee, and Yuanzhi Li · 2018
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jonathan A Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Cited alongside, same era.
Yin Tat Lee and Aaron Sidford · 2013
Cited alongside, same era.
Navigating central path with electrical flows: From flows to matchings, and back
Aleksander Madry · 2013
Cited alongside, same era.
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2013
Cited alongside, same era.
Interior point methods of mathematical programming
Tamás Terlaky · 2013
Cited alongside, same era.
Solving sdd linear systems in nearly m log 1 / 2 n m\log^{1/2}n time
Michael B Cohen, Rasmus Kyng, Gary L Miller, Jakub W Pachocki, Richard Peng, Anup B Rao, and Shen Chen Xu · 2014
Cited alongside, same era.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Cited alongside, same era.
Solving directed laplacian systems in nearly-linear time through sparse LU factorizations
Michael B Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B Rao, and Aaron Sidford · 2018
Closest in time.
Tight cell probe bounds for succinct boolean matrix-vector multiplication
Diptarka Chakraborty, Lior Kamma, and Kasper Green Larsen · 2018
Closest in time.
Incomplete nested dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman, and Peng Zhang · 2018
Closest in time.
Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor
Francois Le Gall and Florent Urrutia · 2018
Closest in time.
Limits on the universal method for matrix multiplication
Josh Alman · 2019
Closest in time.
Solving empirical risk minimization in the current matrix multiplication time
Yin Tat Lee, Zhao Song, and Qiuyi Zhang · 2019
Closest in time.
Solving tall dense linear programs in nearly linear time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song · 2020
Closest in time.
Training (overparametrized) neural networks in near-linear time
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein · 2020
Closest in time.
A deterministic linear program solver in current matrix multiplication time
Jan van den Brand · 2020
Closest in time.
Barriers for rectangular matrix multiplication
Matthias Christandl, François Le Gall, Vladimir Lysikov, and Jeroen Zuiddam · 2020
Closest in time.
Mongoose: A learnable lsh framework for efficient neural network training
Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re · 2020
Closest in time.
A faster interior point method for semidefinite programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song · 2020
Closest in time.
An improved cutting plane method for convex optimization, convex-concave games and its applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong · 2020
Closest in time.
Faster dynamic matrix inverse for faster lps
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang · 2020
Closest in time.
Breaking the n n -pass barrier: A streaming algorithm for maximum weight bipartite matching
S Cliff Liu, Zhao Song, and Hengjie Zhang · 2020
Closest in time.
Oblivious sketching-based central path method for solving linear programming problems
Zhao Song and Zheng Yu · 2020
Closest in time.