# Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model

arXiv: https://arxiv.org/abs/2301.09203 · HTML: https://mlsanity.com/paper/2301.09203/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 35 references that are in the map.
- First posted on arXiv 22 Jan 2023.

## Builds on (most cited first, 18 of 18)

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014)
- [Preventing False Discovery in Interactive Data Analysis is Hard](https://mlsanity.com/paper/1408.1655/) (2014)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [The Adversarial Robustness of Sampling](https://mlsanity.com/paper/1906.11327/) (2019)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds](https://mlsanity.com/paper/2111.03980/) (2021)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Separating Adaptive Streaming from Oblivious Streaming](https://mlsanity.com/paper/2101.10836/) (2021)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Adversarially Robust Streaming via Dense--Sparse Trade-offs](https://mlsanity.com/paper/2109.03785/) (2021)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)

## Abstract (arXiv)

Streaming algorithms are typically analyzed in the oblivious setting, where we assume that the input stream is fixed in advance. Recently, there is a growing interest in designing adversarially robust streaming algorithms that must maintain utility even when the input stream is chosen adaptively and adversarially as the execution progresses. While several fascinating results are known for the adversarial setting, in general, it comes at a very high cost in terms of the required space. Motivated by this, in this work we set out to explore intermediate models that allow us to interpolate between the oblivious and the adversarial models. Specifically, we put forward the following two models: (1) *The advice model*, in which the streaming algorithm may occasionally ask for one bit of advice. (2) *The bounded interruptions model*, in which we assume that the adversary is only partially adaptive. We present both positive and negative results for each of these two models. In particular, we present generic reductions from each of these models to the oblivious model. This allows us to design robust algorithms with significantly improved space complexity compared to what is known in the plain adversarial model.