mlsanityData to 7 Oct 2026

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

arXiv 2301.09203 ↗First posted 22 Jan 2023cs.DS cs.CR cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

18 of 35 references.

References · 18

  1. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  2. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  3. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
  4. 2015Differentially Private Release and Learning of Threshold Functionscited by 58
  5. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  6. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
  7. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 30
  8. 2020A Framework for Adversarially Robust Streaming Algorithmscited by 21
  9. 2020Adversarially Robust Streaming Algorithms via Differential Privacycited by 21
  10. 2019The Adversarial Robustness of Samplingcited by 18
  11. 2021Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Boundscited by 17
  12. 2020Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimatorscited by 16
6 more
  1. 2022~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimizationcited by 16
  2. 2021Separating Adaptive Streaming from Oblivious Streamingcited by 9
  3. 2021A Framework for Adversarial Streaming via Differential Privacy and Difference Estimatorscited by 9
  4. 2021Adversarially Robust Streaming via Dense--Sparse Trade-offscited by 7
  5. 2022On the Robustness of CountSketch to Adaptive Inputscited by 5
  6. 2022Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputscited by 2

Built on by

Not cited yet.