Optimality of Frequency Moment Estimation

Estimating the second frequency moment of a stream up to $(1\pm \epsilon )$ multiplicative error requires at most $O(\log n\mathrm{/}{\epsilon }^2)$ bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least $\mathrm{\Omega }(\log n+1\mathrm{/}{\epsilon }^2)$ space is needed. We prove an optimal lower bound of $\mathrm{\Omega }(\log \left(n{\epsilon }^2\right)\mathrm{/}{\epsilon }^2)$ for all $\epsilon =\mathrm{\Omega }(1\mathrm{/}\sqrt{n})$. Note that when $\epsilon >n^{-1\mathrm{/}2+c}$, where $c>0$, our lower bound matches the classic upper bound of AMS. For smaller values of $\epsilon$ we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound.