TY - GEN
T1 - Optimality of Frequency Moment Estimation
AU - Braverman, Mark
AU - Zamir, Or
N1 - Publisher Copyright:
© 2025 Owner/Author.
PY - 2025/6/15
Y1 - 2025/6/15
N2 - Estimating the second frequency moment of a stream up to (1±ϵ) multiplicative error requires at most O(logn / ϵ2) bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least ω(logn + 1/ϵ2) space is needed. We prove a tight lower bound of ω(log(n ϵ2 ) / ϵ2) for all ϵ = ω(1/√n). Note that 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 holds also for the more general problem of p-th frequency moment estimation for the range of pϵ (1,2], giving a tight bound in the only remaining range to settle the optimal space complexity of estimating frequency moments.
AB - Estimating the second frequency moment of a stream up to (1±ϵ) multiplicative error requires at most O(logn / ϵ2) bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least ω(logn + 1/ϵ2) space is needed. We prove a tight lower bound of ω(log(n ϵ2 ) / ϵ2) for all ϵ = ω(1/√n). Note that 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 holds also for the more general problem of p-th frequency moment estimation for the range of pϵ (1,2], giving a tight bound in the only remaining range to settle the optimal space complexity of estimating frequency moments.
KW - Communication Complexity
KW - Frequency Moments
KW - Information Theory
KW - Streaming Algorithms
UR - https://www.scopus.com/pages/publications/105009772931
UR - https://www.scopus.com/inward/citedby.url?scp=105009772931&partnerID=8YFLogxK
U2 - 10.1145/3717823.3718171
DO - 10.1145/3717823.3718171
M3 - Conference contribution
AN - SCOPUS:105009772931
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 360
EP - 370
BT - STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing
A2 - Koucky, Michal
A2 - Bansal, Nikhil
PB - Association for Computing Machinery
T2 - 57th Annual ACM Symposium on Theory of Computing, STOC 2025
Y2 - 23 June 2025 through 27 June 2025
ER -