Single Pass Spectral Sparsification in Dynamic Streams

DOI10.1137/141002281zbMath1359.68295arXiv1407.1289OpenAlexW2591972614MaRDI QIDQ2968162

Yin Tat Lee, Aaron Sidford, C. N. Musco, C. P. Musco, Michael Kapralov

Publication date: 10 March 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1289

zbMATH Keywords

sparse recoverystreamingspectral sparsificationgraph sketchlinear sketch

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Randomized algorithms (68W20)

Related Items (20)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Graph coarsening: from scientific computing to machine learning ⋮ Maximum Matching in Turnstile Streams ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Unnamed Item ⋮ Single-pass streaming algorithms to partition graphs into few forests ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Unnamed Item ⋮ Correlation clustering in data streams ⋮ Unnamed Item ⋮ Querying a Matrix Through Matrix-Vector Products. ⋮ Better streaming algorithms for the maximum coverage problem ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectral sparsification in the semi-streaming setting
• User-friendly tail bounds for sums of random matrices
• Pseudorandom generators for space-bounded computation
• On graph problems in a semi-streaming model
• Spectral sparsification via random spanners
• Spectral Sparsification in Dynamic Graph Streams
• Approximate Sparse Recovery: Optimizing Time and Measurements
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Spanners and sparsifiers in dynamic streams
• Single Pass Spectral Sparsification in Dynamic Streams
• Uniform Sampling for Matrix Approximation
• Spectral Sparsification of Graphs
• Low-Rank Approximation and Regression in Input Sparsity Time
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Graph Sparsification in the Semi-streaming Model
• Numerical linear algebra in the streaming model
• Probability Inequalities for Sums of Bounded Random Variables
• A Nearly-m log n Time Solver for SDD Linear Systems
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Graph Sparsification by Effective Resistances

This page was built for publication: Single Pass Spectral Sparsification in Dynamic Streams