Fetching the paper…
Reading the bibliography…
In this paper we provide an $\tilde{O}(nd+d^{3})$ time randomized algorithm for solving linear programs with $d$ variables and $n$ constraints with high probability.
Etude critique de la notion de collectif
Jean Ville · 1939
Earlier work this paper cites.
Maximization of a linear function of variables subject to linear inequalities
George B Dantzig · 1951
Earlier work this paper cites.
Gaussian elimination is not optimal
Volker Strassen · 1969
Earlier work this paper cites.
Finite dimensional subspaces of L p {L}_{p}
D. Lewis · 1978
Earlier work this paper cites.
Polynomial algorithms in linear programming
Leonid G Khachiyan · 1980
Earlier work this paper cites.
On the asymptotic complexity of matrix multiplication
Don Coppersmith and Shmuel Winograd · 1982
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
Earlier work this paper cites.
The asymptotic spectrum of tensors and the exponent of matrix multiplication
Volker Strassen · 1986
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.
Approximation of zonoids by zonotopes
Jean Bourgain, Joram Lindenstrauss, and V Milman · 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
Pravin M Vaidya · 1989
Earlier work this paper cites.
Matrix multiplication via arithmetic progressions
Don Coppersmith and Shmuel Winograd · 1990
Earlier work this paper cites.
Reducing the parallel complexity of certain linear programming problems (extended abstract)
Pravin M. Vaidya · 1990
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 A Nemirovsky · 1991
Earlier work this paper cites.
Path-following methods for linear programming
Clovis C Gonzaga · 1992
Earlier work this paper cites.
On the implementation of a primal-dual interior point method
Sanjay. Mehrotra · 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.
Interior-point polynomial algorithms in convex programming
Yurii Nesterov and Arkadii Semenovich 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.
Volumetric path following algorithms for linear programming
Kurt M. Anstreicher · 1996
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2002
Earlier work this paper cites.
An improved data stream summary: the count-min sketch and its applications
Graham Cormode and Shan Muthukrishnan · 2004
Earlier work this paper cites.
Dynamic transitive closure via dynamic matrix inverse (extended abstract)
Piotr Sankowski · 2004
Cited alongside, same era.
Approximate nearest neighbors and the fast johnson-lindenstrauss transform
Nir Ailon and Bernard Chazelle · 2006
Cited alongside, same era.
Stable signal recovery from incomplete and inaccurate measurements
Emmanuel J Candes, Justin K Romberg, and Terence Tao · 2006
Cited alongside, same era.
Compressed sensing
David L. Donoho · 2006
Cited alongside, same era.
Finding the frequent items in streams of data
Graham Cormode and Marios Hadjieleftheriou · 2009
Cited alongside, same era.
Approximate sparse recovery: optimizing time and measurements
Anna C Gilbert, Yi Li, Ely Porat, and Martin J Strauss · 2010
Cited alongside, same era.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Later among the works it cites.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Later among the works it cites.
ℓ p \ell_{p} row sampling by lewis weights
Michael B. Cohen and Richard Peng · 2015
Later among the works it cites.
Efficient inverse maintenance and faster algorithms for linear programming
Yin Tat Lee and Aaron Sidford · 2015
Later among the works it cites.
A faster cutting plane method and its implications for combinatorial and convex optimization
Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
On the complexity of matrix multiplication
Andrew James Stothers · 2010
Cited alongside, same era.
Fast moment estimation in data streams in optimal space
Daniel M Kane, Jelani Nelson, Ely Porat, and David P Woodruff · 2011
Cited alongside, same era.
Randomized algorithms for matrices and data
Michael W. Mahoney · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Interior point algorithms: theory and analysis
Yinyu Ye · 2011
Cited alongside, same era.
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
Mikkel Thorup and Yin Zhang · 2012
Cited alongside, same era.
Iterative methods, combinatorial optimization, and linear programming beyond the universal barrier
Aaron Daniel Sidford · 2015
Later among the works it cites.
Nearly tight oblivious subspace embeddings by trace inequalities
Michael B. Cohen · 2016
Later among the works it cites.
Sparse recovery and Fourier sampling
Haitham Al Hassanieh · 2016
Later among the works it cites.
Faster algorithms for convex and combinatorial optimization
Yin Tat Lee · 2016
Later among the works it cites.
Heavy hitters via cluster-preserving clustering
Kasper Green Larsen, Jelani Nelson, Huy L Nguyên, and Mikkel Thorup · 2016
Later among the works it cites.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2017
Later among the works it cites.
Optimality of the johnson-lindenstrauss lemma
Kasper Green Larsen and Jelani Nelson · 2017
Later among the works it cites.
Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor
Francois Le Gall and Florent Urrutia · 2018
Later among the works it cites.
Iterative refinement for lp-norm regression
Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva · 2019
Later among the works it cites.
Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds
Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak · 2019
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
Michael B Cohen, Yin Tat Lee, and Zhao Song · 2019
Later among the works it cites.
Fully dynamic spectral vertex sparsifiers and applications
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng · 2019
Later among the works it cites.
Solving linear programs with r a n k \sqrt{rank} linear system solves
Yin Tat Lee and Aaron Sidford · 2019
Later among the works it cites.
Solving empirical risk minimization in the current matrix multiplication time
Yin Tat Lee, Zhao Song, and Qiuyi Zhang · 2019
Later among the works it cites.
Stronger L2/L2 compressed sensing; without iterating
Vasileios Nakos and Zhao Song · 2019
Later among the works it cites.
Matrix Theory: Optimization, Concentration and Algorithms
Zhao Song · 2019
Later among the works it cites.
Relative error tensor low rank approximation
Zhao Song, David P Woodruff, and Peilin Zhong · 2019
Later among the works it cites.
A deterministic linear program solver in current matrix multiplication time
Jan van den Brand · 2020
Closest in time.
Dynamic streaming spectral sparsification in nearly linear time and space
Michael Kapralov, Navid Nouri, Aaron Sidford, and Jakab Tardos · 2020
Closest in time.