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