Zero-one frequency laws
DOI10.1145/1806689.1806729zbMATH Open1293.68095OpenAlexW2040088116MaRDI QIDQ2875154FDOQ2875154
Authors: Vladimir Braverman, Rafail Ostrovsky 
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806729
Recommendations
- Optimal approximations of the frequency moments of data streams
- An improved data stream algorithm for frequency moments
- Universal sketches for the frequency negative moments and other decreasing streaming sums
- Optimal space lower bounds for all frequency moments
- On Estimating Frequency Moments of Data Streams
Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Database theory (68P15)
Cited In (11)
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Distributing frequency-dependent data stream computations
- Sketching and embedding are equivalent for norms
- Title not available (Why is that?)
- Zero-one laws for sliding windows and universal sketches
- Model counting meets \(F_0\) estimation
- Tight bounds for the subspace sketch problem with applications
- Universal sketches for the frequency negative moments and other decreasing streaming sums
- Continuous monitoring of \(\ell_p\) norms in data streams
- Okun's law across time and frequencies
- Towards Optimal Moment Estimation in Streaming and Distributed Models
This page was built for publication: Zero-one frequency laws
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875154)
