On the exact space complexity of sketching and streaming small norms

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

Cited in

(32)

Towards Optimal Moment Estimation in Streaming and Distributed Models
On approximating functions of the singular values in a stream
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
Estimating hybrid frequency moments of data streams
On deterministic sketching and streaming for sparse recovery and norm estimation
On deterministic sketching and streaming for sparse recovery and norm estimation
Towards Optimal Moment Estimation in Streaming and Distributed Models
Tracking the l_2 Norm with Constant Update Time
Lower Bounds for Testing Computability by Small Width OBDDs
scientific article; zbMATH DE number 7561590 (Why is no real title available?)
Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
A unified framework for linear dimensionality reduction in L1
On approximating matrix norms in data streams
Perfect \(L_p\) sampling in a data stream
Streaming symmetric norms via measure concentration
Correlation clustering in data streams
Arithmetic sketching
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

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)