mlsanityData to 7 Oct 2026

A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

arXiv 2107.14527 ↗First posted 30 Jul 2021cs.DS cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

Classical streaming algorithms operate under the (not always reasonable) assumption that the input stream is fixed in advance. Recently, there is a growing interest in designing robust streaming algorithms that provide provable guarantees even when the input stream is chosen adaptively as the execution progresses. We propose a new framework for robust streaming that combines techniques from two recently suggested frameworks by Hassidim et al. [NeurIPS 2020] and by Woodruff and Zhou [FOCS 2021]. These recently suggested frameworks rely on very different ideas, each with its own strengths and weaknesses. We combine these two frameworks into a single hybrid framework that obtains the ``best of both worlds'', thereby solving a question left open by Woodruff and Zhou.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 18 of its 41 references that are in the map. First posted on arXiv 30 Jul 2021.

Builds on

18 of 41 references.

References · 18

  1. 2021Adaptive Machine Unlearningcited by 164
  2. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  3. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  4. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
  5. 2015Differentially Private Release and Learning of Threshold Functionscited by 58
  6. 2019A New Analysis of Differential Privacy's Generalization Guaranteescited by 36
  7. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  8. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
  9. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 30
  10. 2020A Framework for Adversarially Robust Streaming Algorithmscited by 21
  11. 2020Adversarially Robust Streaming Algorithms via Differential Privacycited by 21
  12. 2019The Adversarial Robustness of Samplingcited by 18
6 more
  1. 2018The Limits of Post-Selection Generalizationcited by 16
  2. 2020Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimatorscited by 16
  3. 2021Adversarial Robustness of Streaming Algorithms through Importance Samplingcited by 13
  4. 2021Separating Adaptive Streaming from Oblivious Streamingcited by 9
  5. 2021Generalization in the Face of Adaptivity: A Bayesian Perspectivecited by 7
  6. 2017Concentration Bounds for High Sensitivity Functions Through Differential Privacycited by 1

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 3; 2024: 1; 2025: 2.

9 papers.

  1. 2022Adaptive Data Analysis with Correlated Observationscited by 9
  2. 2022On the Robustness of CountSketch to Adaptive Inputscited by 5
  3. 2023Streaming Algorithms for Learning with Experts: Deterministic Versus Robustcited by 3
  4. 2022Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputscited by 2
  5. 2023Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Modelcited by 0
  6. 2023Adversarially Robust Distributed Count Tracking via Partial Differential Privacycited by 0
  7. 2024Fast White-Box Adversarial Streaming Without a Random Oraclecited by 0
  8. 2025The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimationcited by 0
  9. 2025Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programmingcited by 0