On the exact space complexity of sketching and streaming small norms

zbMATH Open1288.68126MaRDI QIDQ5417697FDOQ5417697

Authors: Daniel M. Kane, Jelani Nelson, David P. Woodruff 

Publication date: 22 May 2014

Recommendations

• On approximating matrix norms in data streams
• Continuous monitoring of \(\ell_p\) norms in data streams
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Perfect \(L_p\) sampling in a data stream
• On approximating functions of the singular values in a stream

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of data (68P99)

Cited In (32)

• Space-efficient estimation of statistics over sub-sampled streams
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• A Framework for Adversarially Robust Streaming Algorithms
• Approximating Approximate Pattern Matching
• Everywhere-Tight Information Cost Tradeoffs for Augmented Index
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• On deterministic sketching and streaming for sparse recovery and norm estimation
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Estimating hybrid frequency moments of data streams
• Tracking the l_2 Norm with Constant Update Time
• Lower Bounds for Testing Computability by Small Width OBDDs
• Title not available (Why is that?)
• Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
• Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
• On approximating matrix norms in data streams
• Perfect \(L_p\) sampling in a data stream
• A unified framework for linear dimensionality reduction in L1
• Streaming symmetric norms via measure concentration
• Arithmetic sketching
• Correlation clustering in data streams
• On randomized sketching algorithms and the Tracy-Widom law
• Certifying equality with limited interaction
• Density estimation for shift-invariant multidimensional distributions
• Continuous monitoring of \(\ell_p\) norms in data streams
• High probability frequency moment sketches
• Revisiting frequency moment estimation in random order streams
• On sketching the \(q\) to \(p\) norms
• Periodicity and cyclic shifts via linear sketches
• Adversarially robust streaming algorithms via differential privacy
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• On approximating functions of the singular values in a stream

This page was built for publication: On the exact space complexity of sketching and streaming small norms

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