Zero-one frequency laws

DOI10.1145/1806689.1806729MaRDI QIDQ2875154zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

data streamsrandomized algorithmstheory of computation

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25)

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

Cited in

(11)

• Okun's law across time and frequencies
• scientific article; zbMATH DE number 58300 (Why is no real title available?)
• Sketching and embedding are equivalent for norms
• Continuous monitoring of _p norms in data streams
• Tight bounds for the subspace sketch problem with applications
• Zero-one laws for sliding windows and universal sketches
• Universal sketches for the frequency negative moments and other decreasing streaming sums
• Distributing frequency-dependent data stream computations
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Model counting meets \(F_0\) estimation

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)