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)

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

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)