Wednesday, May 5, 2021 - 12:00pm to 1:00pm
Location:
Virtual Presentation - ET Remote Access - ZoomSpeaker:
SAMSON ZHOU, Postdoctoral Researcher https://samsonzhou.github.io/Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
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. 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 ε is 1/ε2, which shows, up to logarithmic factors, that there is no overhead over the standard insertion-only data stream model for these problems.
Zoom Participation. See announcement.