Fetching the paper…
Reading the bibliography…
We study the problem of sketching an input graph, so that given the sketch, one can estimate the weight of any cut in the graph within factor $1+\epsilon$.
Ramanujan graphs
A. Lubotzky, R. Phillips, and P. Sarnak · 1988
Earlier work this paper cites.
On the second eigenvalue of a graph
A. Nilli · 1991
Earlier work this paper cites.
On the number of small cuts in a graph
M. R. Henzinger and D. P. Williamson · 1996
Earlier work this paper cites.
On the edge-expansion of graphs
N. Alon · 1997
Earlier work this paper cites.
Minimum cuts in near-linear time
D. R. Karger · 2000
Earlier work this paper cites.
Randomized approximation schemes for cuts and flows in capacitated graphs
A. A. Benczúr and D. R. Karger · 2002
Earlier work this paper cites.
Random sampling in residual graphs
D. R. Karger and M. S. Levine · 2002
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
D. A. Spielman and S.-H. Teng · 2004
Earlier work this paper cites.
Graph sparsification in the semi-streaming model
K. J. Ahn and S. Guha · 2009
Earlier work this paper cites.
Expander flows, geometric embeddings and graph partitioning
S. Arora, S. Rao, and U. Vazirani · 2009
Earlier work this paper cites.
Expanders via random spanning trees
N. Goyal, L. Rademacher, and S. Vempala · 2009
Cited alongside, same era.
Graph sparsification via refinement sampling
A. Goel, M. Kapralov, and S. Khanna · 2010
Cited alongside, same era.
Approaching optimality for solving SDD linear systems
I. Koutis, G. L. Miller, and R. Peng · 2010
Cited alongside, same era.
Fast approximation algorithms for cut-based problems in undirected graphs
A. Madry · 2010
Cited alongside, same era.
A general framework for graph sparsification
W. S. Fung, R. Hariharan, N. J. Harvey, and D. Panigrahi · 2011
Cited alongside, same era.
A nearly-
I. Koutis, G. L. Miller, and R. Peng · 2011
Cited alongside, same era.
Single pass sparsification in the streaming model with edge deletions
A. Goel, M. Kapralov, and I. Post · 2012
Later among the works it cites.
Spectral sparsification via random spanners
M. Kapralov and R. Panigrahy · 2012
Later among the works it cites.
Information lower bounds via self-reducibility
M. Braverman, A. Garg, D. Pankratov, and O. Weinstein · 2013
Later among the works it cites.
Spectral sparsification in the semi-streaming setting
J. A. Kelner and A. Levin · 2013
Later among the works it cites.
Interlacing families i: Bipartite ramanujan graphs of all degrees
A. Marcus, D. A. Spielman, and N. Srivastava · 2013
Later among the works it cites.
When distributed computation is communication expensive
D. P. Woodruff and Q. Zhang · 2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Graph sparsification by effective resistances
D. A. Spielman and N. Srivastava · 2011
Cited alongside, same era.
Spectral sparsification of graphs
D. A. Spielman and S.-H. Teng · 2011
Cited alongside, same era.
Graph sketches: Sparsification, spanners, and subgraphs
K. J. Ahn, S. Guha, and A. McGregor · 2012
Cited alongside, same era.
Twice-ramanujan sparsifiers
J. D. Batson, D. A. Spielman, and N. Srivastava · 2012
Cited alongside, same era.
Approximating
A. A. Benczúr and D. R. Karger
Cited in the paper.
Breaking the multicommodity flow barrier for
J. Sherman
Cited in the paper.
Later among the works it cites.
A sketching algorithm for spectral graph sparsification
J. Chen, B. Qin, D. P. Woodruff, and Q. Zhang · 2014
Closest in time.
Single pass spectral sparsification in dynamic streams
M. Kapralov, Y. T. Lee, C. Musco, C. Musco, and A. Sidford · 2014
Closest in time.
Sketching cuts in graphs and hypergraphs
D. Kogan and R. Krauthgamer · 2015
Closest in time.
The distributed complexity of large-scale graph processing
H. Klauck, D. Nanongkai, G. Pandurangan, and P. Robinson · 2015
Closest in time.