Johns Hopkins Algorithms and Complexity
https://www.cs.jhu.edu/~mdinitz/theory
America/New_York
America/New_York
America/New_York
20221106T020000
-0400
-0500
EST
20230312T020000
-0500
-0400
EDT
ai1ec-358@www.cs.jhu.edu/~mdinitz/theory
20221126T134557Z
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.
20210414T120000
20210414T130000
0
[Theory Seminar] Samson Zhou
free