Adversarial Streaming: A Survey of Robust Algorithm Design

Explore the fundamentals of adversarial streaming algorithms in this 59-minute lecture delivered by Moshe Shechner from Tel Aviv University. Gain insights into the evolution from classical streaming algorithms, which assume fixed input streams, to robust streaming algorithms designed for adaptive environments. Learn about various methods for converting oblivious streaming algorithms into robust versions, and understand the limitations of the CountSketch algorithm in adversarial settings. Delve into recent research findings that challenge traditional assumptions about streaming algorithms and discover how modern approaches handle dynamically changing input streams. Master key concepts presented by Shechner, a PhD candidate in computer science at Tel Aviv University, whose research focuses on the intersection of streaming algorithms and adversarial environments under the guidance of Dr. Uri Stemmer and Prof. Edith Cohen.