Estimating the second frequency moment of a stream up to (1 ± ε) multiplicative error requires at most O(log n / ε²) bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least Ω(log n + 1/ε²) space is needed.

We prove a tight lower bound of Ω(log(nε²) / ε²) for all ε = Ω(1/√n).

Notably, when ε > n^(-1/2 + c), where c > 0, our lower bound matches the classic upper bound of AMS. For smaller values of ε, we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound.

Based on a joint work with Mark Braverman.