Fetching the paper…
Reading the bibliography…
Given a separation oracle for a convex set $K \subset \mathbb{R}^n$ that is contained in a box of radius $R$, the goal is to either compute a point in $K$ or prove that $K$ does not contain a ball of radius $\epsilon$.
Maximization of a linear function of variables subject to linear inequalities
George B Dantzig · 1947
Earlier work this paper cites.
The stability of out-input matrices
Max A Woodbury · 1949
Earlier work this paper cites.
Inverting modified matrices
Max A Woodbury · 1950
Earlier work this paper cites.
Existence of an equilibrium for a competitive economy
Kenneth J Arrow and Gerard Debreu · 1954
Earlier work this paper cites.
A finite algorithm for the linear exchange model
B Curtis Eaves · 1975
Earlier work this paper cites.
On the number of multiplications required for matrix multiplication
Roger W Brockett and David Dobkin · 1976
Earlier work this paper cites.
Evaluation of the information complexity of mathematical programming problems
David B Yudin and Arkadii S Nemirovski · 1976
Earlier work this paper cites.
Cut-off method with space extension in convex programming problems
Naum Z Shor · 1977
Earlier work this paper cites.
Finite dimensional subspaces of ℓ p \ell_{p}
D. Lewis · 1978
Earlier work this paper cites.
Polynomial algorithms in linear programming
Leonid G Khachiyan · 1980
Earlier work this paper cites.
Rapid multiplication of rectangular matrices
Don Coppersmith · 1982
Earlier work this paper cites.
Job matching, coalition formation, and gross substitutes
Alexander S Kelso Jr and Vincent P Crawford · 1982
Earlier work this paper cites.
One algorithm for finding solutions of the arrow-debreu model
EI Nenakov and ME Primak · 1983
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
Arkadii Semenovich Nemirovsky and David Borisovich Yudin · 1983
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.
Matrix multiplication via arithmetic progressions
Don Coppersmith and Shmuel Winograd · 1987
Earlier work this paper cites.
The method of inscribed ellipsoids
Leonid G Khachiyan, Sergei Pavlovich Tarasov, and I. I. Erlikh · 1988
Earlier work this paper cites.
Approximation of zonoids by zonotopes
Jean Bourgain, Joram Lindenstrauss, and V Milman · 1989
Earlier work this paper cites.
Linear exchange economies
Bernard Cornet · 1989
Earlier work this paper cites.
Self-concordant functions and polynomial time methods in convex programming. preprint, central economic & mathematical institute, ussr acad
YE Nesterov and AS Nemirovskii · 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.
Analysis of numerical methods
Eugene Isaacson and Herbert Bishop Keller · 1994
Earlier work this paper cites.
Efficient methods in convex programming
Arkadi Nemirovski · 1994
Earlier work this paper cites.
A cutting plane algorithm for convex programming that uses analytic centers
David S Atkinson and Pravin M Vaidya · 1995
Earlier work this paper cites.
Information-based complexity of convex programming
Arkadi Nemirovski · 1995
Earlier work this paper cites.
Algorithms for approximate calculation of the minimum of a convex function from its values
V Yu Protasov · 1996
Earlier work this paper cites.
ibundle: An efficient ascending price bundle auction
David C Parkes · 1999
Earlier work this paper cites.
Ascending auctions with package bidding
Lawrence M Ausubel and Paul R Milgrom · 2002
Cited alongside, same era.
Solving convex programs by random walks
Dimitris Bertsimas and Santosh Vempala · 2002
Cited alongside, same era.
An ascending-price generalized vickrey auction
David C Parkes and Lyle H Ungar · 2002
Cited alongside, same era.
Dynamic transitive closure via dynamic matrix inverse
Piotr Sankowski · 2004
Cited alongside, same era.
Simulated annealing for convex optimization
Adam Tauman Kalai and Santosh Vempala · 2006
Cited alongside, same era.
Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization
László Lovász and Santosh Vempala · 2006
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.
An improved combinatorial polynomial algorithm for the linear arrow-debreu market
Ran Duan, Jugal Garg, and Kurt Mehlhorn · 2016
Later among the works it cites.
A rational convex program for linear arrow-debreu markets
Nikhil R Devanur, Jugal Garg, and László A Végh · 2016
Later among the works it cites.
Faster algorithms for convex and combinatorial optimization
Yin Tat Lee · 2016
Later among the works it cites.
Computing maximum flow with augmenting electrical flows
Aleksander Madry · 2016
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 ascending vickrey auctions for heterogeneous objects
Sven de Vries, James Schummer, and Rakesh V Vohra · 2007
Cited alongside, same era.
A polynomial time algorithm for computing an arrow–debreu market equilibrium for linear utilities
Kamal Jain · 2007
Cited alongside, same era.
Market equilibrium via a primal–dual algorithm for a convex program
Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani · 2008
Cited alongside, same era.
A path to the arrow–debreu competitive market equilibrium
Yinyu Ye · 2008
Cited alongside, same era.
New convex programs and distributed algorithms for fisher markets with linear and spending constraint utilities
Benjamin Birnbaum, N Devanur, and Lin Xiao · 2010
Cited alongside, same era.
Spending constraint utilities with applications to the adwords market
Vijay V Vazirani · 2010
Cited alongside, same era.
Weighted low rank approximations with provable guarantees
Ilya Razenshteyn, Zhao Song, and David P Woodruff · 2016
Later among the works it cites.
László A Végh · 2016
Later among the works it cites.
A New Strongly Polynomial Algorithm for Computing Fisher Market Equilibria with Spending Constraint Utilities
Zi Wang · 2016
Later among the works it cites.
Random Fourier features for kernel ridge regression: Approximation bounds and statistical guarantees
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh · 2017
Later among the works it cites.
Input sparsity time low-rank approximation via ridge leverage score sampling
Michael B Cohen, Cameron Musco, and Christopher Musco · 2017
Later among the works it cites.
Computing walrasian equilibria: fast algorithms and structural properties
Renato Paes Leme and Sam Chiu-wai Wong · 2017
Later among the works it cites.
Fast regression with an ℓ ∞ {\ell}_{\infty} guarantee
Eric Price, Zhao Song, and David P. Woodruff · 2017
Later among the works it cites.
Low rank approximation with entrywise ℓ 1 \ell_{1} -norm error
Zhao Song, David P Woodruff, and Peilin Zhong · 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.
Efficient convex optimization with membership oracles
Yin Tat Lee, Aaron Sidford, and Santosh S Vempala · 2018
Later among the works it cites.
An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild · 2018
Later among the works it cites.
A universal sampling method for reconstructing signals with simple Fourier transforms
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh · 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.
A near-optimal algorithm for approximating the John ellipsoid
Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang · 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.
A strongly polynomial algorithm for linear exchange markets
Jugal Garg and László A Végh · 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.
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.
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.
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.
Leverage score sampling, neural tangent kernel, and kernel ridge regression
Jason Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu · 2020
Closest in time.