Fetching the paper…
Reading the bibliography…
We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs.
Random Walks and Electric Networks
Peter G. Doyle and J. Laurie Snell · 1984
Earlier work this paper cites.
Fast algorithms for finding nearest common ancestors
Dov Harel and Robert Endre Tarjan · 1984
Earlier work this paper cites.
Fibonacci heaps and their uses in improved network optimization algorithms
Michael L. Fredman and Robert Endre Tarjan · 1987
Earlier work this paper cites.
Random walks on graphs
László Lovász · 1993
Earlier work this paper cites.
Lecture notes on graphs and networks, October 2007
Daniel A. Spielman · 2007
Earlier work this paper cites.
Fast counting of triangles in large real networks without counting: Algorithms and laws
Charalampos E Tsourakakis · 2008
Earlier work this paper cites.
Graph sparsification by effective resistances
D. Spielman and N. Srivastava · 2011
Earlier work this paper cites.
Using petal-decompositions to build a low stretch spanning tree
Ittai Abraham and Ofer Neiman · 2012
Earlier work this paper cites.
Spectral sparsification via random spanners
Michael Kapralov and Rina Panigrahy · 2012
Earlier work this paper cites.
Colorful triangle counting and a mapreduce implementation
Rasmus Pagh and Charalampos E Tsourakakis · 2012
Earlier work this paper cites.
User-friendly tail bounds for sums of random matrices
Joel A. Tropp · 2012
Earlier work this paper cites.
Spectral sparsification of graphs: theory and algorithms
Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng · 2013
Earlier work this paper cites.
Fully dynamic (1+ e)-approximate matchings
Manoj Gupta and Richard Peng · 2013
Cited alongside, same era.
Deterministic fully dynamic data structures for vertex cover and matching
Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano · 2014
Cited alongside, same era.
Listing triangles
Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick · 2014
Cited alongside, same era.
Michael B Cohen, Gary L Miller, Jakub W Pachocki, Richard Peng, and Shen Chen Xu · 2014
Cited alongside, same era.
Efficient maximum flow algorithms
Andrew V Goldberg and Robert E Tarjan · 2014
Cited alongside, same era.
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.
Faster spectral sparsification of laplacian and SDDM matrix polynomials
Gorav Jindal and Pavel Kolev · 2015
Later among the works it cites.
Faster spectral sparsification and numerical algorithms for SDD matrices
Ioannis Koutis, Alex Levin, and Richard Peng · 2015
Later among the works it cites.
On fully dynamic graph sparsifiers
Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng · 2016
Later among the works it cites.
Personal Communication, 2016
Yu Cheng and Dehua Cheng · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai · 2014
Cited alongside, same era.
Simple parallel and distributed algorithms for spectral graph sparsification
Ioannis Koutis · 2014
Cited alongside, same era.
An efficient parallel solver for SDD linear systems
Richard Peng and Daniel A. Spielman · 2014
Cited alongside, same era.
Shortest-path queries in static networks
Christian Sommer · 2014
Cited alongside, same era.
Sketching as a tool for numerical linear algebra
David P Woodruff et al · 2014
Cited alongside, same era.
Efficient sampling for Gaussian graphical models via spectral sparsification
Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng · 2015
Cited alongside, same era.
Sampling random spanning trees faster than matrix multiplication
David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva · 2016
Later among the works it cites.
Incremental exact min-cut in poly-logarithmic amortized update time
Gramoz Goranci, Monika Henzinger, and Mikkel Thorup · 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
Later among the works it cites.
Approximate gaussian elimination for laplacians-fast, sparse, and simple
Rasmus Kyng and Sushant Sachdeva · 2016
Later among the works it cites.
Input sparsity time low-rank approximation via ridge leverage score sampling
Michael B. Cohen, Cameron Musco, and Christopher Musco · 2017
Closest in time.
A framework for analyzing resparsification algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva · 2017
Closest in time.