Seminar

We typically have seminars on Wednesdays at noon in Malone 228.  All seminar announcements will be sent to the theory mailing list.

Apr
14
Wed
[Theory Seminar] Samson Zhou
Apr 14 @ 12:00 pm – 1:00 pm

Speaker: Samson Zhou
Affiliation: Carnegie Mellon University

Title: Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

Abstract:
We introduce difference estimators for data stream computation, which provide approximations to F(v)-F(u) for frequency vectors v,u and a given function F. We show how to use such estimators to carefully trade error for memory in an iterative manner. The function F is generally non-linear, and we give the first difference estimators for the frequency moments F_p for p between 0 and 2, as well as for integers p>2. Using these, we resolve a number of central open questions in adversarial robust streaming and sliding window models.

For both models, we obtain algorithms for norm estimation whose dependence on epsilon is 1/epsilon^2, which shows, up to logarithmic factors, that there is no overhead over the standard insertion-only data stream model for these problems.

Sep
6
Wed
[Theory Seminar] Welcome Back / Introductions
Sep 6 @ 12:00 pm – 1:00 pm
Oct
25
Wed
[Theory Seminar] Zeyu Guo
Oct 25 @ 12:00 pm – 1:00 pm

Speaker: Zeyu Guo
Affiliation: Ohio State University

Title: TBD

Abstract: TBD