Fetching the paper…
Reading the bibliography…
We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus few extra edges.
Fast approximation algorithms for cut-based problems in undirected graphs
Aleksander Madry · 1975
Earlier work this paper cites.
A scheme for fast parallel communication
Leslie G. Valiant · 1982
Earlier work this paper cites.
Isoperimetric inequalities for graphs, and superconcentrators
N Alon and V.D Milman · 1985
Earlier work this paper cites.
There is a planar graph almost as good as the complete graph
P Chew · 1986
Earlier work this paper cites.
Ramanujan graphs
A. Lubotzky, R. Phillips, and P. Sarnak · 1988
Earlier work this paper cites.
Sparse partitions (extended abstract)
Baruch Awerbuch and David Peleg · 1990
Earlier work this paper cites.
Random walks on graphs: A survey
László Lovász · 1993
Earlier work this paper cites.
Sparsification: a technique for speeding up dynamic graph algorithms
David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig · 1997
Earlier work this paper cites.
Concentration inequalities and martingale inequalities: a survey
Fan Chung and Linyuan Lu · 2006
Earlier work this paper cites.
A tractable approach to finding closest truncated-commute-time neighbors in large graphs
Purnamrita Sarkar and Andrew W Moore · 2007
Earlier work this paper cites.
Fully dynamic algorithm for graph spanners with poly-logarithmic update time
Surender Baswana and Soumojit Sarkar · 2008
Earlier work this paper cites.
Optimal hierarchical decompositions for congestion minimization in networks
Harald Racke · 2008
Earlier work this paper cites.
Tractable algorithms for proximity search on large graphs
Purnamrita Sarkar · 2010
Earlier work this paper cites.
Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices
Daniel A. Spielman · 2010
Earlier work this paper cites.
The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
Shang-Hua Teng · 2010
Earlier work this paper cites.
Improved dynamic algorithms for maintaining approximate shortest paths under deletions
Aaron Bernstein and Liam Roditty · 2011
Earlier work this paper cites.
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
Earlier work this paper cites.
Electric routing and concurrent flow cutting
Jonathan A. Kelner and Petar Maymounkov · 2011
Earlier work this paper cites.
A nearly-m log n time solver for SDD linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2011
Earlier work this paper cites.
Graph sparsification by effective resistances
D. Spielman and N. Srivastava · 2011
Earlier work this paper cites.
Spectral sparsification of graphs
D. Spielman and S. Teng · 2011
Earlier work this paper cites.
Spectral sparsification of graphs
Daniel A. Spielman and Shang-Hua Teng · 2011
Cited alongside, same era.
Fully dynamic randomized algorithms for graph spanners
Surender Baswana, Sumeet Khurana, and Soumojit Sarkar · 2012
Cited alongside, same era.
Twice-Ramanujan sparsifiers
Joshua 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.
Spectral sparsification via random spanners
Michael Kapralov and Rina Panigrahy · 2012
Cited alongside, same era.
Faster algorithms for computing the stationary distribution, simulating random walks, and more
Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu · 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.
Scalable algorithms for data and network analysis
Shang-Hua Teng · 2016
Later among the works it cites.
Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Joel A. Tropp · 2012
Cited alongside, same era.
Spectral sparsification of graphs: theory and algorithms
Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng · 2013
Cited alongside, same era.
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford · 2014
Cited alongside, same era.
Approaching optimality for solving sdd linear systems
I. Koutis, G. Miller, and R. Peng · 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.
Computing cut-based hierarchical decompositions in almost linear time
Harald Racke, Chintan Shah, and Hanjo Taubig · 2014
Cited alongside, same era.
Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B Rao, Aaron Sidford, and Adrian Vladu · 2017
Later among the works it cites.
Optimal lower bounds for sketching graph cuts
Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan · 2017
Later among the works it cites.
Sampling random spanning trees faster than matrix multiplication
David Durfee, Rasmus Kyng, John Peebles, Anup B Rao, and Sushant Sachdeva · 2017
Later among the works it cites.
David Durfee, John Peebles, Richard Peng, and Anup B. Rao · 2017
Later among the works it cites.
On computing min-degree elimination orderings
Matthew Fahrbach, Gary L. Miller, Richard Peng, Saurabh Sawlani, Junxing Wang, and Shen Chen Xu · 2017
Later among the works it cites.
Cascades and myopic routing in nonhomogeneous kleinberg’s small world model
Jie Gao, Grant Schoenebeck, and Fang-Yi Yu · 2017
Later among the works it cites.
A framework for analyzing resparsification algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva · 2017
Later among the works it cites.
Approximate Gaussian Elimination
Rasmus Kyng · 2017
Later among the works it cites.
An SDP-based algorithm for linear-sized spectral sparsification
Yin Tat Lee and He Sun · 2017
Later among the works it cites.
An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild · 2017
Later among the works it cites.
Massively parallel algorithms for finding well-connected components in sparse graphs
Sepehr Assadi, Xiaorui Sun, and Omri Weinstein · 2018
Closest in time.
Nearly tight bounds for sandpile transience on the grid
David Durfee, Matthew Fahrbach, Yu Gao, and Tao Xiao · 2018
Closest in time.
Fully dynamic effective resistances
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng · 2018
Closest in time.
Current flow group closeness centrality for complex networks
Huan Li, Richard Peng, Liren Shan, Yuhao Yi, and Zhongzhi Zhang · 2018
Closest in time.
Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms
Huan Li and Zhongzhi Zhang · 2018
Closest in time.
Spectrum approximation beyond fast matrix multiplication: Algorithms and hardness
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P. Woodruff · 2018
Closest in time.
Nearly maximum flows in nearly linear time
Jonah Sherman · 2077
Closest in time.