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

randomized algorithmsdata streamstheory of computation

Mathematics Subject Classification ID

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

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)

• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Towards Optimal Moment Estimation in Streaming and Distributed Models
• Distributing frequency-dependent data stream computations
• Sketching and embedding are equivalent for norms
• scientific article; zbMATH DE number 58300 (Why is no real title available?)
• 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

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)