Fetching the paper…
Reading the bibliography…
Recently there has been much interest in "sparsifying" sums of rank one matrices: modifying the coefficients such that only a few are nonzero, while approximately preserving the matrix that results from the sum.
The Lovász bound and some generalizations
R. J. McEliece, E. R. Rodemich, and H. C. Rumsey, Jr · 1978
Earlier work this paper cites.
A comparison of the Delsarte and Lovász bounds
Alexander Schrijver · 1979
Earlier work this paper cites.
Matrix analysis
Roger A. Horn and Charles R. Johnson · 1985
Earlier work this paper cites.
Updating the inverse of a matrix
William W. Hager · 1989
Earlier work this paper cites.
On sparse approximations to randomized strategies and convex combinations
Ingo Althöfer · 1994
Earlier work this paper cites.
Simple strategies for large zero-sum games with applications to complexity theory
Richard J. Lipton and Neal E. Young · 1994
Earlier work this paper cites.
Greedy algorithms by derandomizing unknown distributions
Neal Young · 1994
Earlier work this paper cites.
Randomized rounding without solving the linear program
Neal Young · 1995
Earlier work this paper cites.
Approximate s s - t t min-cuts in O ~ ( n 2 ) \tilde{O}(n^{2}) time
András A. Benczúr and David R. Karger · 1996
Earlier work this paper cites.
Computing sparse approximations deterministically
Thomas Hofmeister and Hanno Lefmann · 1996
Earlier work this paper cites.
Approximating a finite metric by a small number of tree metrics
Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge A. Plotkin · 1998
Earlier work this paper cites.
Adaptive game playing using multiplicative weights
Yoav Freund and Robert E. Schapire · 1999
Earlier work this paper cites.
Random vectors in the isotropic position
Mark Rudelson · 1999
Earlier work this paper cites.
Strong converse for identification via quantum channels
Rudolf Ahlswede and Andreas Winter · 2002
Earlier work this paper cites.
Randomized approximation schemes for cuts and flows in capacitated graphs, 2002
András A. Benczúr and David R. Karger · 2002
Cited alongside, same era.
On the Laplacian eigenvalues and metric parameters of hypergraphs
Juan A. Rodríguez · 2002
Cited alongside, same era.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
Approximation algorithms for semidefinite packing problems with applications to maxcut and graph coloring
Garud Iyengar, David J. Phillips, and Clifford Stein · 2005
Cited alongside, same era.
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 2007
Cited alongside, same era.
Efficient Algorithms using the Multiplicative Weights Update Method
Graph sparsification via refinement sampling, April 2010
Ashish Goel, Michael Kapralov, and Sanjeev Khanna · 2010
Later among the works it cites.
A general framework for graph sparsification, April 2010
Ramesh Hariharan and Debmalya Panigrahi · 2010
Later among the works it cites.
A linear-time algorithm for sparsification of unweighted graphs, May 2010
Ramesh Hariharan and Debmalya Panigrahi · 2010
Later among the works it cites.
Approaching optimality for solving SDD systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010
Later among the works it cites.
Finite volume spaces and sparsification, 2010
Ilan Newman and Yuri Rabinovich · 2010
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Satyen Kale · 2007
Cited alongside, same era.
Sampling from large matrices: An approach through geometric functional analysis
Mark Rudelson and Roman Vershynin · 2007
Cited alongside, same era.
A unified theorem on SDP rank reduction
Anthony Man-Cho So, Yinyu Ye, and Jiawei Zhang · 2008
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2008
Cited alongside, same era.
A note on sums of independent random matrices after Ahlswede-Winter, 2008
Roman Vershynin · 2008
Cited alongside, same era.
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators and applications
Avi Wigderson and David Xiao · 2008
Cited alongside, same era.
Twice-Ramanujan sparsifiers
Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava · 2009
Cited alongside, same era.
Later among the works it cites.
Min-max theorems related to geometric representations of graphs and their SDPs, August 2011
Marcel de Carli Silva and Levent Tunçel · 2011
Closest in time.
A general framework for graph sparsification
Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi · 2011
Closest in time.
Lecture notes for C&O 750: Randomized algorithms, 2011
Nicholas J. A. Harvey · 2011
Closest in time.
Approximating semidefinite packing programs
Garud Iyengar, David J. Phillips, and Clifford Stein · 2011
Closest in time.
A parallel approximation algorithm for positive semidefinite programming
Rahul Jain and Penghui Yao · 2011
Closest in time.
Spectral sparsification in the semi-streaming setting
Jonathan A. Kelner and Alex Levin · 2011
Closest in time.
Sparse quadratic forms and their geometric applications (after batson, spielman and srivastava)
Assaf Naor · 2011
Closest in time.
Towards an SDP-based approach to spectral methods: A nearly-linear time algorithm for graph partitioning and decomposition
Lorenzo Orecchia and Nisheeth K. Vishnoi · 2011
Closest in time.