אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.

Our lower bound also applies to the more general problem of p-th frequency moment estimation for the range of p in (1, 2], providing a tight bound in the only remaining range to settle the optimal space complexity of estimating frequency moments.

Based on a joint work with Mark Braverman.