Separating Adaptive Streaming from Oblivious Streaming

We present a streaming problem for which every adversarially-robust streaming algorithm must use polynomial space, while there exists a classical (oblivious) streaming algorithm that uses only polylogarithmic space. This is the first separation between oblivious streaming and adversarially-robust streaming, and resolves one of the central open questions in adversarial robust streaming.

Adversarial Robustness in Machine Learning Complexity and Algorithms in Graphs Advanced Bandit Algorithms Research

View graph Source

Paper

Similar papers

A Framework for Adversarially Robust Streaming AlgorithmsOmri Ben‐Eliezer, Rajesh Jayaram, David P. Woodruff et al.2020 In Library

Adversarially Robust Streaming via Dense-Sparse Trade-offsOmri Ben‐Eliezer, Talya Eden, Krzysztof Onak2022 · Society for Industrial and Applied Mathematics eBooks In Library

Robust Streaming Against Low-Memory AdversariesOmri Ben-Eliezer, Krzysztof Onak, Sandeep Silwal2025 · arXiv (Cornell University) In Library

Adversarially Robust Streaming Algorithms via Differential PrivacyAvinatan Hassidim, Haim Kaplan, Yishay Mansour et al.2022 · Journal of the ACM In Library

Adversarially Robust Streaming Algorithms via Differential PrivacyAvinatan Hassidim, Haim Kaplan, Y. Mansour et al.2020 · Neural Information Processing Systems · 84 citations In Library

Adversarially Robust Streaming via Dense--Sparse Trade-offsOmri Ben‐Eliezer, Talya Eden, Krzysztof Onak2021 · arXiv (Cornell University) In Library

Fast White-Box Adversarial Streaming Without a Random OracleYing Feng, Aayush Jain, David P. Woodruff2024 · International Conference on Machine Learning · 5 citations In Library

Adversarially Robust and Sliding Window Streaming Algorithms without the OverheadDavid P. Woodruff, Samson Zhou2020 · arXiv (Cornell University) In Library

A Framework for Adversarial Streaming via Differential Privacy and Difference EstimatorsIdan Attias, Edith Cohen, Moshe Shechner et al.2021 · arXiv (Cornell University) · 44 citations In Library

A Framework for Adversarial Streaming Via Differential Privacy and Difference EstimatorsIdan Attias, Edith Cohen, Moshe Shechner et al.2024 · Algorithmica In Library

Source of record

OpenAlex

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal