A Framework for Adversarially Robust Streaming Algorithms
Abstract
We investigate the adversarial robustness of streaming algorithms. In this context, 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 in the streaming literature do not admit sublinear-space deterministic algorithms; on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 31, 2022
- Source ID
- 10.1145/3498334
Entities
People
- David P. Woodruff
- Eylon Yogev
- Omri Ben-Eliezer
- Rajesh Jayaram
Organizations
- Bar-Ilan University
- Carnegie Mellon University
- Google Research
- Massachusetts Institute of Technology
- National Science Foundation
- Office of Naval Research