Fast and Space Efficient Spectral Sparsification in Dynamic Streams

DOI10.1137/1.9781611975994.111MaRDI QIDQ5146894zbMATH OpenOpenAlexFDO

Authors Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975994.111

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(9)

• Spectral sparsification in the semi-streaming setting
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Annotations for Sparse Data Streams
• Spiking neural networks through the lens of streaming algorithms
• Streaming edge coloring with asymptotically optimal colors
• Streaming algorithms for connectivity augmentation
• On the streaming complexity of expander decomposition
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Streaming algorithms for network design

This page was built for publication: Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146894)