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