Fetching the paper…
Reading the bibliography…
We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_\alpha(G)=D-\sum_{r=1}^d\alpha_rD(D^{-1}A)^r$$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $\alpha=(\alpha_1...\alpha_d)$ are nonnegative coefficients with $\sum_{r=1}^d\alpha_r=1$.
An analysis of the finite element method
Gilbert Strang and George J Fix · 1973
Earlier work this paper cites.
A fast algorithm for particle simulations
Leslie Greengard and Vladimir Rokhlin · 1987
Earlier work this paper cites.
Reversible markov chains and random walks on graphs, 2002
David Aldous and Jim Fill · 2002
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.
New streaming algorithms for counting triangles in graphs
Hossein Jowhari and Mohammad Ghodsi · 2005
Earlier work this paper cites.
Faster approximate lossy generalized flow via interior point algorithms
Samuel I. Daitch and Daniel A. Spielman · 2008
Earlier work this paper cites.
Pegasus: A peta-scale graph mining system implementation and observations
U Kang, Charalampos E Tsourakakis, and Christos Faloutsos · 2009
Earlier work this paper cites.
Approaching optimality for solving sdd linear systems
Ioannis Koutis, Gary L Miller, and Richard Peng · 2010
Cited alongside, same era.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng · 2011
Cited alongside, same era.
On p p th roots of stochastic matrices
Nicholas J Higham and Lijing Lin · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikil Srivastava · 2011
Cited alongside, same era.
Spectral sparsification of graphs
Daniel A. Spielman and Shang-Hua Teng · 2011
Cited alongside, same era.
Twice-ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.
Spectral sparsification in the semi-streaming setting
Jonathan A Kelner and Alex Levin · 2013
Later among the works it cites.
A simple, combinatorial algorithm for solving sdd systems in nearly-linear time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Later among the works it cites.
Approximate maximum flow on separable undirected graphs
Gary L Miller and Richard Peng · 2013
Later among the works it cites.
Algorithm Design Using Spectral Graph Theory
Richard Peng · 2013
Later among the works it cites.
Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng · 2014
Later among the works it cites.
An efficient parallel solver for sdd linear systems
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
Po-Ling Loh and Martin J. Wainwright · 2012
Cited alongside, same era.
Richard Peng and Daniel A. Spielman · 2014
Later among the works it cites.
Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Daniel A. Spielman and Shang-Hua Teng · 2014
Later among the works it cites.