The Taub Faculty of Computer Science Events and Talks

A streaming algorithm is given a long sequence of items and seeks to compute or approximate some function of this sequence using a small amount of memory. A body of work has been developed over the last two decades, resulting in optimal streaming algorithms for a wide range of problems. While randomized streaming algorithms are well-studied, the vast majority of them are defined and analyzed in the static setting, where the stream is assumed to be fixed in advance, and only then the randomness of the algorithm is chosen. In many scenarios, this assumption is unrealistic, making the algorithms prone to adversarial attacks, and unfit for real-life applications. I will investigate the adversarial robustness of streaming algorithms. An algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. I will describe general-purpose methods we have developed to transform standard streaming algorithms to be secure in the adversarial model. These are the first streaming algorithms to work in this model. Bio: Dr. Eylon Yogev is a postdoc at Tel Aviv University hosted by Omer Paneth and Nir Bitasnky and co-affiliated at Boston University hosted by Ran Canetti. Prior to that, he was a research fellow at the Simons Institute and a postdoc at the Technion hosted by Yuval Ishai. He received his Ph.D. and M.Sc. from the Weizmann Institute of Science under the supervision of Moni Naor and completed his B.Sc. in Computer Science at Tel Aviv University. Eylon is broadly interested in cryptography, with a focus on its interplay with the area of algorithm design and analysis.