Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-175 | 4th November 2024 13:05

Optimality of Frequency Moment Estimation

RSS-Feed




TR24-175
Authors: Mark Braverman, Or Zamir
Publication: 17th November 2024 16:22
Downloads: 68
Keywords: 


Abstract:

Estimating the second frequency moment of a stream up to $(1\pm\varepsilon)$ multiplicative error requires at most $O(\log n / \varepsilon^2)$ bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least $\Omega(\log n + 1/\varepsilon^{2})$ space is needed.
We prove an optimal lower bound of $\Omega\left(\log \left(n \varepsilon^2 \right) / \varepsilon^2\right)$ for all $\varepsilon = \Omega(1/\sqrt{n})$.
Note that when $\varepsilon>n^{-1/2 + c}$, where $c>0$, our lower bound matches the classic upper bound of AMS. For smaller values of $\varepsilon$ we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound.
Our lower bound holds also for the more general problem of $p$-th frequency moment estimation for the range of $p\in (1,2]$, giving a tight bound in the only remaining range to settle the optimal space complexity of estimating frequency moments.



ISSN 1433-8092 | Imprint