Optimal space lower bounds for all frequency moments

zbMATH Open1317.68059MaRDI QIDQ5501255FDOQ5501255

Publication date: 3 August 2015

Recommendations

Optimal approximations of the frequency moments of data streams
An optimal algorithm for large frequency moments using \(O(n^{1-2/k})\) bits
A Tight Lower Bound for High Frequency Moment Estimation with Small Error
An improved data stream algorithm for frequency moments
An information statistics approach to data stream and communication complexity

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Theory of data (68P99)

Cited In (39)

Towards unified approximate pattern matching for Hamming and \(L_1\) distance
Recent advances in text-to-pattern distance algorithms
The space complexity of approximating the frequency moments
Space‐efficient tracking of persistent items in a massive data stream
Robust lower bounds for communication and stream computation
A Note on Estimating Hybrid Frequency Moment of Data Streams
A Framework for Adversarially Robust Streaming Algorithms
Title not available (Why is that?)
Approximating Approximate Pattern Matching
Everywhere-Tight Information Cost Tradeoffs for Augmented Index
Towards Optimal Moment Estimation in Streaming and Distributed Models
Estimating hybrid frequency moments of data streams
Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)
An information statistics approach to data stream and communication complexity
Hierarchical sampling from sketches: Estimating functions over data streams
Sketching information divergences
Title not available (Why is that?)
Sketching and embedding are equivalent for norms
An improved data stream algorithm for frequency moments
Tight bounds for distributed functional monitoring
Applying approximate counting for computing the frequency moments of long data streams
An optimal algorithm for large frequency moments using \(O(n^{1-2/k})\) bits
On differential privacy and adaptive data analysis with bounded space
Exact lower bound for proportion of maximally embedded beamlet
Tight lower bound for linear sketches of moments
Taylor polynomial estimator for estimating frequency moments
Universal sketches for the frequency negative moments and other decreasing streaming sums
Continuous monitoring of \(\ell_p\) norms in data streams
Optimal approximations of the frequency moments of data streams
Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
Revisiting frequency moment estimation in random order streams
Spiking neural networks through the lens of streaming algorithms
The cost of fault tolerance in multi-party communication complexity
A simple algorithm for approximating the text-to-pattern Hamming distance
Streaming algorithms with one-sided estimation
The Simultaneous Communication of Disjointness with Applications to Data Streams
Towards Optimal Moment Estimation in Streaming and Distributed Models
Zero-one frequency laws
One-sided error communication complexity of gap Hamming distance

This page was built for publication: Optimal space lower bounds for all frequency moments

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