AI4OPT faculty member Barna Saha, a Harry E. Gruber Professor of Computer Science and Information Technologies Endowed Chair, Associate Professor, University of California San Diego is hosting a talk series on "Adversarially Robust Streaming Algorithms.” The first of four talks will be a tutorial-style talk by David Woodruff, a professor at Carnegie Mellon University in the Computer Science Department.

Date: Wednesday, October 5, 2022

Time: 4 pm – 5 pm

Meeting Link: https://syracuseuniversity.zoom.us/j/99153665466

Password: Answer to (101 x 102)

Adversarially Robust Streaming Algorithms

Speaker: David Woodruff

Abstract: A streaming algorithm is given a 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 number of problems. I will start by surveying some of these problems. I will then 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. While deterministic streaming algorithms are inherently robust, many central problems do not admit sublinear-space deterministic algorithms; on the other hand, space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. I will survey work showing for a number of streaming problems, one can obtain algorithms that are adversarially robust with a small overhead in their memory requirements.

Bio: David Woodruff is a professor at Carnegie Mellon University in the Computer Science Department. Before that he was a research scientist at the IBM Almaden Research Center. His research interests include data stream algorithms, distributed algorithms, machine learning, numerical linear algebra, optimization, sketching, and sparse recovery. He is the recipient of the 2020 Simons Investigator Award, the 2014 Presburger Award, and Best Paper Awards at STOC 2013, PODS 2010, and PODS, 2020. At IBM he was a member of the Academy of Technology and a Master Inventor.

 For more information and to view upcoming talks, please visit Virtual Talk Series.