קולוקוויום בביה"ס למדעי המחשב -Adversarially Robust Streaming Algorithms

Abstract:

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 these 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.

Link:  https://calendar.google.com/calendar/embed?src=taucs.colloquium%40gmail.com&ctz=Asia%2FJerusalem