Fetching the paper…
Reading the bibliography…
We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs.
Inequalities for the moments of the eigenvalues of the Schrödinger equation and their relation to Sobolev inequalities
E Lieb and W Thirring · 1976
Earlier work this paper cites.
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.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
Approaching optimality for solving SDD linear systems
Ioannis Koutis, Gary L Miller, and Richard Peng · 2010
Earlier work this paper cites.
A nearly- m log n m\log n time solver for SDD linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2011
Earlier work this paper cites.
Randomized algorithms for matrices and data
Michael W Mahoney · 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.
Improved spectral sparsification and numerical algorithms for SDD matrices
Ioannis Koutis, Alex Levin, and Richard Peng · 2012
Cited alongside, same era.
On contact points of convex bodies
Nikhil Srivastava · 2012
Cited alongside, same era.
An elementary proof of the restricted invertibility theorem
Daniel A Spielman and Nikhil Srivastava · 2012
Cited alongside, same era.
User-friendly tail bounds for sums of random matrices
Joel A. Tropp · 2012
Cited alongside, same era.
A matrix hyperbolic cosine algorithm and applications
Anastasios Zouzias · 2012
Cited alongside, same era.
Nearly maximum flows in nearly linear time
Jonah Sherman · 2013
Later among the works it cites.
Thrifty approximations of convex bodies by polytopes
Alexander Barvinok · 2014
Later among the works it cites.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2014
Later among the works it cites.
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford · 2014
Later among the works it cites.
Path finding methods for linear programming: Solving linear programs in O ~ ( rank ) \widetilde{O}(\sqrt{\textrm{rank}}) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jonathan A Kelner and Alex Levin · 2013
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2013
Cited alongside, same era.
Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem
Adam Marcus, Daniel A Spielman, and Nikhil Srivastava · 2013
Cited alongside, same era.
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
Closest in time.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Closest in time.
Sparsified Cholesky solvers for SDD linear systems
Yin Tat Lee, Richard Peng, and Daniel A Spielman · 2015
Closest in time.