Fetching the paper…
Reading the bibliography…
Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning.
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.
The variation of the spectrum of a normal matrix
A. J. Hoffman and H. W. Wielandt · 1953
Earlier work this paper cites.
Evaluation of the information complexity of mathematical programming problems
David B Yudin and Arkadi 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.
Polynomial algorithms in linear programming
Leonid G Khachiyan · 1980
Earlier work this paper cites.
The ellipsoid method and its consequences in combinatorial optimization
Martin Grötschel, László Lovász, and Alexander Schrijver · 1981
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
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.
Self-concordant functions and polynomial time methods in convex programming. preprint, central economic & mathematical institute, ussr acad
Yurii Nesterov and Arkadi Nemirovski · 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.
Degeneration and complexity of bilinear maps: some asymptotic spectra
Volker Strassen · 1991
Earlier work this paper cites.
Conic formulation of a convex programming problem and duality
Yurii Nesterov and Arkadi Nemirovski · 1992
Earlier work this paper cites.
Approximate graph coloring by semidefinite programming
David Karger, Rajeev Motwani, and Madhu Sudan · 1994
Earlier work this paper cites.
Interior-point polynomial algorithms in convex programming
Yurii Nesterov and 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.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X Goemans and David P Williamson · 1995
Earlier work this paper cites.
Semidefinite programming
Lieven Vandenberghe and Stephen P. Boyd · 1996
Cited alongside, same era.
Algebraic complexity theory
Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi · 1997
Cited alongside, same era.
The volumetric barrier for semidefinite programming
Kurt M Anstreicher · 2000
Cited alongside, same era.
A Mathematical View of Interior-point Methods in Convex Optimization
James Renegar · 2001
Cited alongside, same era.
Solving convex programs by random walks
Dimitris Bertsimas and Santosh Vempala · 2002
Cited alongside, same era.
Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method
Jean-Louis Goffin and Jean-Philippe Vial · 2002
Cited alongside, same era.
Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver
Zeyuan Allen Zhu, Yin Tat Lee, and Lorenzo Orecchia · 2016
Later among the works it cites.
An algorithm for komlós conjecture matching banaszczyk
Nikhil Bansal, Daniel Dadush, and Shashwat Garg · 2016
Later among the works it cites.
Sublinear time algorithms for approximate semidefinite programming
Dan Garber and Elad Hazan · 2016
Later among the works it cites.
Faster algorithms for convex and combinatorial optimization
Yin Tat Lee · 2016
Later among the works it cites.
Follow the compressed leader: faster online learning of eigenvectors and faster mmwu
Zeyuan Allen-Zhu and Yuanzhi Li · 2017
Later among the works it cites.
Algorithmic discrepancy beyond partial coloring
Nikhil Bansal and Shashwat Garg · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Properties of a cutting plane method for semidefinite programming
Kartik Krishnan and John E Mitchell · 2003
Cited alongside, same era.
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 2007
Cited alongside, same era.
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2009
Cited alongside, same era.
QIP = PSPACE
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous · 2011
Cited alongside, same era.
A parallel approximation algorithm for positive semidefinite programming
Rahul Jain and Penghui Yao · 2011
Cited alongside, same era.
Matrix Analysis
Roger A. Horn and Charles R. Johnson · 2012
Cited alongside, same era.
Later among the works it cites.
Non-convex matrix completion against a semi-random adversary
Yu Cheng and Rong Ge · 2018
Later among the works it cites.
Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor
François Le Gall and Florent Urrutia · 2018
Later among the works it cites.
On a generalization of iterated and randomized rounding
Nikhil Bansal · 2019
Later among the works it cites.
High-dimensional robust mean estimation in nearly-linear time
Yu Cheng, Ilias Diakonikolas, and Rong Ge · 2019
Later among the works it cites.
Faster algorithms for high-dimensional robust covariance estimation
Yu Cheng, Ilias Diakonikolas, Rong Ge, and David Woodruff · 2019
Later among the works it cites.
A rank-1 sketch for matrix multiplicative weights
Yair Carmon, John C. Duchi, Aaron Sidford, and Kevin Tian · 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.
Scalable semidefinite programming, 2019
Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher · 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.
Positive semidefinite programming: mixed, parallel, and width-independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian · 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.
An $\widetilde\mathcalo(m/\varepsilonˆ3.5)$-cost algorithm for semidefinite programs with diagonal constraints
Yin Tat Lee and Swati Padmanabhan · 2020
Closest in time.