TCS+ talk: Wednesday, April 9, Or Zamir, Tel Aviv University
Clement Canonne
Our next talk will take place on Wednesday, April 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Or Zamir from Tel Aviv University will speak about "Optimality of Frequency Moment Estimation" (abstract below).
(Note that the talk is on April 9th, not April 2nd, to accommodate the FOCS deadline.)
Please sign up on the online form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk if you wish to join the talk as an individual or a group. Registration is /not/ required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The link to the recording will also be posted on our website afterwards.)
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.
Clement Canonne
The link for tomorrow's TCS+ talk has been posted: you will be able to join tomorrow, starting at 12:50pm ET:
https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09
(you will need a to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: 'Clement Canonne' via TCS+ <tcsplus_...@googlegroups.com>
Sent: Friday, March 28, 2025 5:49 PM
To: 'Clement Canonne' via TCS+
Subject: TCS+ talk: Wednesday, April 9, Or Zamir, Tel Aviv University
Dear TCS+ followers,
Our next talk will take place on Wednesday, April 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Or Zamir from Tel Aviv University will speak about "Optimality of Frequency Moment Estimation" (abstract below).
(Note that the talk is on April 9th, not April 2nd, to accommodate the FOCS deadline.)
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.
You received this message because you are subscribed to the Google Groups "TCS+" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tcsplus_announ...@googlegroups.com.
To view this discussion visit https://url.au.m.mimecastprotect.com/s/TgK7C81V0PTwV1YY2s1hXUycEzR?domain=groups.google.com.
For more options, visit https://url.au.m.mimecastprotect.com/s/0chlC91WPRTYyQ22lu3iOUq5WUP?domain=groups.google.com.