Fetching the paper…
Reading the bibliography…
We introduce a new notion of graph sparsificaiton based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original.
A lower bound for smallest eigenvalue of laplacian
J. Cheeger · 1970
Earlier work this paper cites.
Efficiency of a good but not linear set union algorithm
R. E. Tarjan · 1975
Earlier work this paper cites.
The eigenvalues of random symmetric matrices
Z. Füredi and J. Komlós · 1981
Earlier work this paper cites.
A survey of preconditioned iterative methods for linear systems of algebraic equations
O. Axelsson · 1985
Earlier work this paper cites.
Ramanujan graphs
A. Lubotzky, R. Phillips, and P. Sarnak · 1988
Earlier work this paper cites.
Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
G. A. Margulis · 1988
Earlier work this paper cites.
Probabilistic construction of deterministic algorithms: Approximating packing integer programs
Prabhakar Raghavan · 1988
Earlier work this paper cites.
There are planar graphs almost as good as the complete graph
Paul Chew · 1989
Earlier work this paper cites.
Approximate counting, uniform generation and rapidly mixing Markov chains
Alistair Sinclair and Mark Jerrum · 1989
Earlier work this paper cites.
Geometric bounds for eigenvalues of markov chains
Persi Diaconis and Daniel Stroock · 1991
Earlier work this paper cites.
The Laplacian spectrum of graphs
Bojan Mohar · 1991
Earlier work this paper cites.
Approximating s-t minimum cuts in O(n 2
András A. Benczúr and David R. Karger · 1996
Cited alongside, same era.
Spectral Graph Theory
Fan R. K. Chung · 1997
Cited alongside, same era.
Numerical Linear Algebra
L. N. Trefethen and D. Bau · 1997
Cited alongside, same era.
Modern graph theory
Béla Bollobás · 1998
Cited alongside, same era.
Balls and bins: a study in negative dependence
Devdatt Dubhashi and Desh Ranjan · 1998
Cited alongside, same era.
Fast computation of low rank matrix approximations
Dimitris Achlioptas and Frank McSherry · 2001
Cited alongside, same era.
Algebraic Graph Theory
Chris Godsil and Gordon Royle · 2001
Cited alongside, same era.
Approximation algorithms for unique games
Lucan Trevisan · 2005
Later among the works it cites.
Local graph partitioning using pagerank vectors
Reid Andersen, Fan Chung, and Kevin Lang · 2006
Later among the works it cites.
Support-graph preconditioners
M. Bern, J. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo · 2006
Later among the works it cites.
Spectral norm of random matrices
Van Vu · 2007
Later among the works it cites.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2008
Closest in time.
Daniel A. Spielman and Shang-Hua Teng · 2008
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Support theory for preconditioning
Erik G. Boman and Bruce Hendrickson · 2003
Cited alongside, same era.
On clusterings: Good, bad and spectral
Ravi Kannan, Santosh Vempala, and Adrian Vetta · 2004
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.
Closest in time.
Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Daniel A. Spielman and Shang-Hua Teng · 2008
Closest in time.
Finding sparse cuts locally using evolving sets
Reid Andersen and Yuval Peres · 2009
Closest in time.
Twice-Ramanujan sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2009
Closest in time.
Approaching optimality for solving sdd systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010
Closest in time.