Fetching the paper…
Reading the bibliography…
For any undirected and weighted graph $G=(V,E,w)$ with $n$ vertices and $m$ edges, we call a sparse subgraph $H$ of $G$, with proper reweighting of the edges, a $(1+\varepsilon)$-spectral sparsifier if \[ (1-\varepsilon)x^{\intercal}L_Gx\leq x^{\intercal} L_{H} x\leq (1+\varepsilon) x^{\intercal} L_Gx \] holds for any $x\in\mathbb{R}^n$, where $L_G$ and $L_{H}$ are the respective Laplacian matrices of $G$ and $H$.
There are planar graphs almost as good as the complete graph
L. Paul Chew · 1989
Earlier work this paper cites.
Approximating s s - t t minimum cuts in O ~ ( n 2 ) \widetilde{O}(n^{2}) time
András Benczúr and David Karger · 1996
Earlier work this paper cites.
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
Haim Avron and Sivan Toledo · 2011
Earlier work this paper cites.
A parallel approximation algorithm for positive semidefinite programming
Rahul Jain and Penghui Yao · 2011
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
Spectral sparsification of graphs
Daniel A. Spielman and Shang-Hua Teng · 2011
Earlier work this paper cites.
Twice-Ramanujan sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.
Faster and simpler width-independent parallel algorithms for positive semidefinite programming
Richard Peng and Kanat Tangwongsan · 2012
Cited alongside, same era.
A matrix hyperbolic cosine algorithm and applications
Anastasios Zouzias · 2012
Cited alongside, same era.
Spectral sparsification of graphs: theory and algorithms
Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng · 2013
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2013
Cited alongside, same era.
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2013
An efficient parallel solver for SDD linear systems
Richard Peng and Daniel A. Spielman · 2014
Later among the works it cites.
Spectral sparsification and regret minimization beyond multiplicative updates
Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia · 2015
Later among the works it cites.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Later among the works it cites.
Constructing linear-sized spectral sparsification in almost-linear time
Yin Tat Lee and He Sun · 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.
Sparsified Cholesky and multigrid solvers for connection Laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman · 2016
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Later among the works it cites.