Adversarial Streaming, Differential Privacy, and Adaptive Data Analysis

Abstract: Streaming algorithms are algorithms for processing large data streams, using only a limited amount of memory. Classical streaming algorithms typically work under the assumption that the input stream is chosen independently from the internal state of the algorithm. Recently, there is a growing interest in studying streaming algorithms that maintain utility also when the input stream is chosen by an adaptive adversary, possibly as a function of previous estimates given by the streaming algorithm. Such streaming algorithms are said to be adversarially-robust. In this talk I will highlight two connections with adversarial streaming: A connection with the notion of differential privacy (leading to positive results for adversarial streaming) and a connection with the recent line of work on adaptive data analysis (leading to negative results for adversarial streaming).

This talk is based on joint works with Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Kobbi Nissim.