Fetching the paper…
Reading the bibliography…
Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g.
A polynomial algorithm in linear programming
Leonid G Khachiyan · 1979
Earlier work this paper cites.
Combinatorial Optimization: Algorithms and Complexity
Christos H. Papadimitriou and Kenneth Steiglitz · 1982
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
Earlier work this paper cites.
An algorithm for linear programming which requires o(((m+n)nˆ2 + (m+n)ˆ1.5 n)l) arithmetic operations
Pravin M. Vaidya · 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.
Pathways to the optimal set in linear programming
Nimrod Megiddo · 1989
Earlier work this paper cites.
Self-concordant functions and polynomial-time methods in convex programming
Yu Nesterov and Arkadi Nemirovskiy · 1989
Earlier work this paper cites.
A new algorithm for minimizing convex functions over convex sets (extended abstract)
Pravin M. Vaidya · 1989
Earlier work this paper cites.
Speeding-up linear programming using fast matrix multiplication (extended abstract)
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
Yurii Nesterov and Arkadii Nemirovskii · 1991
Earlier work this paper cites.
A subexponential randomized simplex algorithm (extended abstract)
Gil Kalai · 1992
Earlier work this paper cites.
A technique for bounding the number of iterations in path following algorithms
Pravin M Vaidya and David S Atkinson · 1993
Earlier work this paper cites.
An o( √ \surd nl)-iteration homogeneous and self-dual linear programming algorithm
Yinyu Ye, Michael J. Todd, and Shinji Mizuno · 1994
Earlier work this paper cites.
A new infinity-norm path following algorithm for linear programming
Kurt M. Anstreicher and Robert A. Bosch · 1995
Earlier work this paper cites.
Las vegas algorithms for linear and integer programming when the dimension is small
Kenneth L. Clarkson · 1995
Earlier work this paper cites.
Volumetric path following algorithms for linear programming
Kurt M. Anstreicher · 1996
Cited alongside, same era.
On linear-time deterministic algorithms for optimization problems in fixed dimension
Bernard Chazelle and Jivr’i Matouvsek · 1996
Cited alongside, same era.
A subexponential bound for linear programming
Jivr’i Matouvsek, Micha Sharir, and Emo Welzl · 1996
Cited alongside, same era.
Self-scaled barriers and interior-point methods for convex programming
Yurii E. Nesterov and Michael J. Todd · 1997
Cited alongside, same era.
Linear programming in o([n3/ln n]l) operations
Kurt M. Anstreicher · 1999
Cited alongside, same era.
Product range spaces, sensitive sampling, and derandomization
Hervé Brönnimann, Bernard Chazelle, and Jivr’i Matouvsek · 1999
Cited alongside, same era.
Improved deterministic algorithms for linear programming in low dimensions
Timothy M. Chan · 2016
Later among the works it cites.
Derandomization beyond connectivity: Undirected laplacian systems in nearly logarithmic space
Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil P. Vadhan · 2017
Later among the works it cites.
Further limitations of the known approaches for matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2018
Later among the works it cites.
Limits on all known (and some unknown) approaches to matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2018
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
Michael B. Cohen, Yin Tat Lee, and Zhao Song · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A minimum spanning tree algorithm with inverse-ackermann type complexity
Bernard Chazelle · 2000
Cited alongside, same era.
Minimum cuts in near-linear time
David R. Karger · 2000
Cited alongside, same era.
An optimal minimum spanning tree algorithm
Seth Pettie and Vijaya Ramachandran · 2002
Cited alongside, same era.
Dynamic transitive closure via dynamic matrix inverse (extended abstract)
Piotr Sankowski · 2004
Cited alongside, same era.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Cited alongside, same era.
Path finding i: Solving linear programs with õ(sqrt(rank)) linear system solves
Yin Tat Lee and Aaron Sidford · 2013
Cited alongside, same era.
Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor
Francois Le Gall and Florent Urrutia · 2018
Later among the works it cites.
Limits on the universal method for matrix multiplication
Josh Alman · 2019
Closest in time.
Barriers for fast matrix multiplication from irreversibility
Matthias Christandl, Péter Vrana, and Jeroen Zuiddam · 2019
Closest in time.
Distributed edge connectivity in sublinear time
Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak · 2019
Closest in time.
Deterministic edge connectivity in near-linear time
Ken-ichi Kawarabayashi and Mikkel Thorup · 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.
Matrix Theory : Optimization, Concentration and Algorithms
Zhao Song · 2019
Closest in time.
Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds
Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak · 2019
Closest in time.
Barriers for rectangular matrix multiplication
Matthias Christandl, François Le Gall, Vladimir Lysikov, and Jeroen Zuiddam · 2020
Closest in time.