TCS+ talk *this coming week*: Wednesday, April 9, Or Zamir, Tel Aviv University
Clement Canonne
This is a reminder that the next TCS+ talk is taking place this coming week, Wednesday, April 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://sites.google.com/view/tcsplus/welcome/past-talks after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: http://www.youtube.com/user/TCSplusSeminars.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Or Zamir (Tel Aviv University)
Title: Optimality of Frequency Moment Estimation
Abstract: 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.