Fetching the paper…
Reading the bibliography…
In this paper we consider the problem of computing spectral approximations to graphs in the single pass dynamic streaming model.
Probability inequalities for sums of bounded random variables
Wassily Hoeffding · 1963
Earlier work this paper cites.
Random sampling in cut, flow, and network design problems
David R. Karger · 1994
Earlier work this paper cites.
Approximating S-T minimum cuts in O ~ ( n 2 ) \tilde{O}(n^{2}) time
András A. Benczúr and David R. Karger · 1996
Earlier work this paper cites.
Approximate nearest neighbors: Towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
Database-friendly random projections: Johnson-lindenstrauss with binary coins
Dimitris Achlioptas · 2003
Earlier work this paper cites.
Locality-sensitive hashing scheme based on p-stable distributions
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni · 2004
Earlier work this paper cites.
Graph stream algorithms: A survey
Andrew McGregor · 2004
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.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Alexandr Andoni and Piotr Indyk · 2006
Earlier work this paper cites.
Twice-ramanujan sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2009
Earlier work this paper cites.
Faster generation of random spanning trees
Jonathan A. Kelner and Aleksander Madry · 2009
Earlier work this paper cites.
Approaching optimality for solving SDD linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010
Earlier work this paper cites.
Tight bounds for Lp samplers, finding duplicates in streams, and related problems
Hossein Jowhari, Mert Sağlam, and Gábor Tardos · 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
Daniel A Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
Spectral sparsification of graphs
Daniel A. Spielman and Shang-Hua Teng · 2011
Earlier work this paper cites.
Spectral sparsification of graphs
Daniel A. Spielman and Shang-Hua Teng · 2011
Earlier work this paper cites.
Analyzing graph structure via linear measurements
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2012
Earlier work this paper cites.
Graph sketches: sparsification, spanners, and subgraphs
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2012
Earlier work this paper cites.
Graph sketches: sparsification, spanners, and subgraphs
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2012
Earlier work this paper cites.
Spectral sparsification in dynamic graph streams
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor · 2013
Earlier work this paper cites.
Spectral sparsification of graphs: theory and algorithms
Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng · 2013
Cited alongside, same era.
A unifying framework for ℓ 0 \ell_{0} -sampling algorithms
Graham Cormode and Donatella Firmani · 2013
Cited alongside, same era.
54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA
2013
Cited alongside, same era.
Spectral sparsification in the semi-streaming setting
Jonathan A. Kelner and Alex Levin · 2013
Cited alongside, same era.
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L. Miller, and Richard Peng · 2013
Cited alongside, same era.
Maximum matchings in dynamic graph streams and the simultaneous communication model
Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev · 2016
Later among the works it cites.
Online row sampling
Michael B Cohen, Cameron Musco, and Jakub Pachocki · 2016
Later among the works it cites.
Faster spectral sparsification and numerical algorithms for SDD matrices
Ioannis Koutis, Alex Levin, and Richard Peng · 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.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
Yin Tat Lee and Aaron Sidford · 2013
Cited alongside, same era.
Beyond locality-sensitive hashing
Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya P. Razenshteyn · 2014
Cited alongside, same era.
Solving SDD linear systems in nearly m log 1/2 {}^{\mbox{1/2}} n time
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu · 2014
Cited alongside, same era.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2014
Cited alongside, same era.
Spanners and sparsifiers in dynamic streams
Michael Kapralov and David P. Woodruff · 2014
Cited alongside, same era.
Turnstile streaming algorithms might as well be linear sketches
Yi Li, Huy L. Nguyen, and David P. Woodruff · 2014
Cited alongside, same era.
Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan · 2017
Later among the works it cites.
On estimating maximum matching size in graph streams
Sepehr Assadi, Sanjeev Khanna, and Yang Li · 2017
Later among the works it cites.
Density independent algorithms for sparsifying k-step random walks
Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani · 2017
Later among the works it cites.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, CN Musco, CP Musco, and Aaron Sidford · 2017
Later among the works it cites.
Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, and Mobin Yahyazadeh · 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.
An sdp-based algorithm for linear-sized spectral sparsification
Yin Tat Lee and He Sun · 2017
Later among the works it cites.
Graph sketching and streaming: New approaches for analyzing massive graphs
Andrew McGregor · 2017
Later among the works it cites.
Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions
Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang · 2018
Later among the works it cites.
Efficient o ~ ( n / ϵ ) {\widetilde{o}}(n/\epsilon) spectral sketches for the laplacian and its pseudoinverse
Arun Jambulapati and Aaron Sidford · 2018
Later among the works it cites.
Efficient spectral sketches for the laplacian and its pseudoinverse
Arun Jambulapati and Aaron Sidford · 2018
Later among the works it cites.
Spectral subspace sparsification
Huan Li and Aaron Schild · 2018
Later among the works it cites.
An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild · 2018
Later among the works it cites.
Faster spectral sparsification in dynamic streams
Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, and Navid Nouri · 2019
Closest in time.
Optimal lower bounds for distributed and streaming spanning forest computation
Jelani Nelson and Huacheng Yu · 2019
Closest in time.