Faculty Recruiting Support CICS

Theory Seminar - Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

10 Mar
Wednesday, 03/10/2021 12:15pm to 1:15pm
Virtual via Zoom
Theory Seminar
Speaker: Samson Zhou

Abstract: 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.

This is joint work with David P. Woodruff

Bio: Samson is a postdoctoral researcher at Carnegie Mellon University, hosted by David P. Woodruff. He received his PhD from Purdue, where he was advised by Greg Frederickson and Elena Grigorescu and hosted by Jeremiah Blocki. He spent a year as a postdoctoral researcher at Indiana University, hosted by Grigory Yaroslavtsev. His research focuses on the theoretical foundations of data science, including sublinear algorithms with an emphasis on streaming algorithms, machine learning, and numerical linear algebra.

Join the Zoom meeting

The CICS Theory Seminar is online, free and open to the public. If you are interested in giving a talk, please email Professor Immerman or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.