Fetching the paper…
Reading the bibliography…
This paper introduces a new robust interior point method analysis for semidefinite programming (SDP).
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.
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.
Rapid multiplication of rectangular matrices
Don Coppersmith · 1982
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.
Polynomial-time iterative methods in linear and quadratic programming
Yu Nesterov · 1988
Earlier work this paper cites.
Polynomial methods in the linear and quadratic-programming
YY Nesterov · 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.
Conic formulation of a convex programming problem and duality
Yurii Nesterov and Arkadi Nemirovski · 1992
Earlier work this paper cites.
.879-approximation algorithms for max cut and max 2sat
Michel X Goemans and David P Williamson · 1994
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.
The geometry of graphs and some of its algorithmic applications
Nathan Linial, Eran London, and Yuri Rabinovich · 1995
Earlier work this paper cites.
Algebraic complexity theory
Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi · 1997
Earlier work this paper cites.
Determinant maximization with linear matrix inequality constraints
Lieven Vandenberghe, Stephen Boyd, and Shao-Po Wu · 1998
Earlier work this paper cites.
The volumetric barrier for semidefinite programming
Kurt M Anstreicher · 2000
Earlier work this paper cites.
A Mathematical View of Interior-point Methods in Convex Optimization
James Renegar · 2001
Earlier work this paper cites.
Solving convex programs by random walks
Dimitris Bertsimas and Santosh Vempala · 2002
Earlier work this paper cites.
Properties of a cutting plane method for semidefinite programming
Kartik Krishnan and John E Mitchell · 2003
Earlier work this paper cites.
o ( log n ) o(\sqrt{\log n}) approximation algorithms for min uncut, min 2cnf deletion, and directed cut problems
Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev · 2005
Earlier work this paper cites.
Haplofreq—estimating haplotype frequencies efficiently
Eran Halperin and Elad Hazan · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Earlier work this paper cites.
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 2007
Cited alongside, same era.
A direct formulation for sparse pca using semidefinite programming
Alexandre d’Aspremont, Laurent El Ghaoui, Michael I Jordan, and Gert RG Lanckriet · 2007
Cited alongside, same era.
High-dimensional analysis of semidefinite relaxations for sparse principal components
Arash A Amini and Martin J Wainwright · 2008
Cited alongside, same era.
Improved approximation algorithms for minimum weight vertex separators
Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee · 2008
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.
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.
Quantum entropy scoring for fast robust mean estimation and improved outlier detection
Yihe Dong, Samuel Hopkins, and Jerry Li · 2019
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A parallel approximation algorithm for positive semidefinite programming
Rahul Jain and Penghui Yao · 2011
Cited alongside, same era.
A parallel approximation algorithm for mixed packing and covering semidefinite programs
Rahul Jain and Penghui Yao · 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.
Canonical barriers on convex cones
Roland Hildebrand · 2014
Cited alongside, same era.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Cited alongside, same era.
Later among the works it cites.
Semialgebraic Proofs and Efficient Algorithm Design
Noah Fleming, Pravesh Kothari, and Toniann Pitassi · 2019
Later among the works it cites.
Solving linear programs with 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.
Relative error tensor low rank approximation
Zhao Song, David P Woodruff, and Peilin Zhong · 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
Later among the works it cites.
A deterministic linear program solver in current matrix multiplication time
Jan van den Brand · 2020
Later among the works it cites.
Barriers for rectangular matrix multiplication
Matthias Christandl, François Le Gall, Vladimir Lysikov, and Jeroen Zuiddam · 2020
Later among the works it cites.
Learning structured distributions from untrusted batches: Faster and simpler
Sitan Chen, Jerry Li, and Ankur Moitra · 2020
Later among the works it cites.
A faster interior point method for semidefinite programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song · 2020
Later among the works it cites.
Positive semidefinite programming: mixed, parallel, and width-independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian · 2020
Later among the works it cites.
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
Later among the works it cites.
Robust sub-gaussian principal component analysis and width-independent schatten packing
Arun Jambulapati, Jerry Li, and Kevin Tian · 2020
Later among the works it cites.
Strong self-concordance and sampling
Aditi Laddha, Yin Tat Lee, and Santosh Vempala · 2020
Later among the works it cites.
An O ~ ( m / ϵ 3.5 ) \widetilde{O}(m/\epsilon^{3.5}) -cost algorithm for semidefinite programs with diagonal constraints
Yin Tat Lee and Swati Padmanabhan · 2020
Later among the works it cites.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2021
Closest in time.
Unifying matrix data structures: Simplifying and speeding up iterative algorithms
Jan van den Brand · 2021
Closest in time.
Terminal embeddings in sublinear time
Yeshwanth Cherapanamjeri and Jelani Nelson · 2021
Closest in time.
Matrix discrepancy from quantum communication
Samuel B Hopkins, Prasad Raghavendra, and Abhishek Shetty · 2021
Closest in time.
Faster dynamic matrix inverse for faster lps
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang · 2021
Closest in time.
Solving sparse linear systems faster than matrix multiplication
Richard Peng and Santosh Vempala · 2021
Closest in time.