Designing Robust Algorithms for Data Streams with Adversarial Generation

Watch a technical lecture exploring the design of robust algorithms for data streams that can handle adversarial inputs, presented by Prof. Amit Chakrabarti from Dartmouth College. Dive into the challenges of modern data stream processing systems that must efficiently handle massive continuous data while maintaining accuracy even when future inputs are influenced by the system's own outputs. Learn about fundamental concepts in adversarially robust streaming algorithms before examining recent research findings on the Missing Item Finding (MIF) problem and graph coloring. Discover how the space requirements and color budgets for these problems are significantly impacted by the available sources of random bits. Benefit from the expertise of Prof. Chakrabarti, a pioneering researcher in theoretical computer science known for developing the concept of "information complexity" and whose work has earned prestigious recognition including a 20-year Test of Time Award from IEEE FOCS.