Fetching the paper…
Reading the bibliography…
We give the first approximation algorithm for mixed packing and covering semidefinite programs (SDPs) with polylogarithmic dependence on width.
Lower bounds for the helmholtz function
Sidney Golden · 1965
Earlier work this paper cites.
Inequality with applications in statistical mechanics
Colin J. Thompson · 1965
Earlier work this paper cites.
Exponential Operators and Parameter Differentiation in Quantum Physics
R. M. Wilcox · 1967
Earlier work this paper cites.
Inequalities for the moments of the eigenvalues of the schrodinger hamiltonian and their relation to sobolev inequalities
E. H. Lieb and W. E. Thirring · 1976
Earlier work this paper cites.
On the shannon capacity of a graph
László Lovász · 1979
Earlier work this paper cites.
Toward a generalized singular value decomposition
C. C. Paige and M. A. Saunders · 1981
Earlier work this paper cites.
A method of solving a convex programming problem with covergence rate O ( 1 / k 2 ) O(1/k^{2})
Yu. Nesterov · 1983
Earlier work this paper cites.
Self-concordant functions and polynomial-time methods in convex programming
Yu. Nesterov and A. S. Nemirovskii · 1989
Earlier work this paper cites.
Estimating the largest eigenvalue by the power and lanczos algorithms with a random start
J. Kuczynski and Henryk Wozniakowski · 1992
Earlier work this paper cites.
A parallel approximation algorithm for positive linear programming
Michael Luby and Noam Nisan · 1993
Earlier work this paper cites.
A sublinear-time randomized approximation algorithm for matrix games
Michael D. Grigoriadis and Leonid G. Khachiyan · 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.
Fast approximation algorithms for fractional packing and covering problems
Serge A. Plotkin, David B. Shmoys, and Éva Tardos · 1995
Earlier work this paper cites.
Semidefinite programming
Lieven Vandenberghe and Stephen P. Boyd · 1996
Earlier work this paper cites.
Approximate graph coloring by semidefinite programming
David R. Karger, Rajeev Motwani, and Madhu Sudan · 1998
Earlier work this paper cites.
The complexity of the matrix eigenproblem
Victor Y. Pan and Zhao Q. Chen · 1999
Earlier work this paper cites.
Sequential and parallel algorithms for mixed packing and covering
Neal E. Young · 2001
Earlier work this paper cites.
An elementary proof of a theorem of johnson and lindenstrauss
Sanjoy Dasgupta and Anupam Gupta · 2003
Earlier work this paper cites.
Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems
Arkadi Nemirovski · 2004
Earlier work this paper cites.
Efficient algorithms for online decision problems
Adam Tauman Kalai and Santosh S. Vempala · 2005
Cited alongside, same era.
A unifying framework for several cutting plane methods for semidefinite programming
Kartik Krishnan and John E. Mitchell · 2006
Cited alongside, same era.
Randomized PCA algorithms with regret bounds that are logarithmic in the dimension
Manfred K. Warmuth and Dima Kuzmin · 2006
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 V. Vazirani · 2009
Cited alongside, same era.
Approximating semidefinite packing programs
Garud Iyengar, David J. Phillips, and Clifford Stein · 2011
Cited alongside, same era.
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.
Di Wang, Michael W. Mahoney, Nishanth Mohan, and Satish Rao · 2015
Later among the works it cites.
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.
Approximating the solution to mixed packing and covering lps in parallel o~(epsilonˆ{-3}) time
Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang · 2016
Later among the works it cites.
Faster and simpler width-independent parallel algorithms for positive semidefinite programming
Richard Peng, Kanat Tangwongsan, and Peng Zhang · 2016
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
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.
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
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.
Approximating the exponential, the lanczos method and an õ( m )-time spectral algorithm for balanced separator
Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi · 2012
Cited alongside, same era.
A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
Michel Baes, Michael Bürgisser, and Arkadi Nemirovski · 2013
Cited alongside, same era.
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.
Hardness results for structured linear systems
Rasmus Kyng and Peng Zhang · 2017
Later among the works it cites.
An sdp-based algorithm for linear-sized spectral sparsification
Yin Tat Lee and He Sun · 2017
Later among the works it cites.
Area-convexity, l ∞ {}_{\mbox{{$\infty$}}} regularization, and undirected multicommodity flow
Jonah Sherman · 2017
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.
Arun Jambulapati, Kirankumar Shiragur, and Aaron Sidford · 2018
Later among the works it cites.
Perron-frobenius theory in nearly linear time: Positive eigenvectors, m-matrices, graph kernels, and other applications
AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, and Aaron Sidford · 2019
Later among the works it cites.
Personal communication, 2019
Zeyuan Allen-Zhu · 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.
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.
Variance reduction for matrix games
Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian · 2019
Later among the works it cites.
Yin Tat Lee and Swati Padmanabhan · 2019
Later among the works it cites.
Packing lps are hard to solve accurately, assuming linear equations are hard
Rasmus Kyng, Di Wang, and Peng Zhang · 2020
Closest in time.