We typically have seminars on Wednesdays at noon in Malone 228. For Fall 2021, we will be having seminars virtually using Zoom in this room. All seminar announcements will be sent to the theory mailing list.
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.