A Tight Lower Bound for High Frequency Moment Estimation with Small Error

DOI10.1007/978-3-642-40328-6_43zbMath1405.68129OpenAlexW8957553MaRDI QIDQ2851890

Yi Li, David P. Woodruff

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40328-6_43

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

Taylor Polynomial Estimator for Estimating Frequency Moments ⋮ The Simultaneous Communication of Disjointness with Applications to Data Streams ⋮ A Framework for Adversarially Robust Streaming Algorithms ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Unnamed Item ⋮ High Probability Frequency Moment Sketches ⋮ Approximating Approximate Pattern Matching ⋮ Quantum Chebyshev's Inequality and Applications ⋮ On Approximating Matrix Norms in Data Streams

This page was built for publication: A Tight Lower Bound for High Frequency Moment Estimation with Small Error