Adversarially Robust Streaming Algorithms

Speaker: Omri Ben-Eliezer , Harvard University

Date: Wednesday, March 17, 2021

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/j/97637459251

Event Type: Seminar

Room Description:

Host: Quanquan Liu, MIT

Contact: Quanquan Liu, quanquan@csail.mit.edu

Relevant URL: https://mit.zoom.us/j/97637459251

Speaker URL: http://www.cs.tau.ac.il/~omrib/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Adversarially Robust Streaming Algorithms

Streaming algorithms are traditionally divided into two categories: deterministic algorithms and randomized ones. These two types of algorithms exhibit a tradeoff between robustness and efficiency; on one hand, deterministic algorithms always return a correct output, but for many important streaming problems, they are provably inefficient. On the other hand, efficient randomized algorithms are known for a very wide range of problems, but their correctness typically relies on the assumption that the stream is fixed in advance, which is commonly unrealistic in practice.

In this talk, I will focus on a middle ground that combines both robustness and efficiency: adversarially robust algorithms, whose output is correct with high probability even when the stream updates are adaptively chosen as a function of previous outputs. This regime has received surprisingly little attention until recently, and many intriguing problems are still open. I will mention some of the recent results, discussing algorithms that are well-suited for the adversarially robust regime (random sampling), algorithms that are not robust (sketching), and efficient techniques to turn algorithms that work in the standard static setting into robust streaming algorithms.

The results demonstrate strong connections between streaming and other areas such as online learning, differential privacy, cryptography, adaptive data analysis and statistics.

Based on joint works with Noga Alon, Yuval Dagan, Rajesh Jayaram, Shay Moran, Moni Naor, David Woodruff, and Eylon Yogev.

Research Areas:
Algorithms & Theory, AI & Machine Learning

Impact Areas:
Big Data

See other events that are part of the Algorithms and Complexity Seminar 2021.

Created by Quanquan Liu Email at Tuesday, March 02, 2021 at 1:21 AM.