# A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

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

## Key facts

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

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

- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [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)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [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)
- [The Limits of Post-Selection Generalization](https://mlsanity.com/paper/1806.06100/) (2018)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Separating Adaptive Streaming from Oblivious Streaming](https://mlsanity.com/paper/2101.10836/) (2021)
- [Generalization in the Face of Adaptivity: A Bayesian Perspective](https://mlsanity.com/paper/2106.10761/) (2021)
- [Concentration Bounds for High Sensitivity Functions Through Differential Privacy](https://mlsanity.com/paper/1703.01970/) (2017)

## Built on by (most cited first, 9 of 9)

- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model](https://mlsanity.com/paper/2301.09203/) (2023)
- [Adversarially Robust Distributed Count Tracking via Partial Differential Privacy](https://mlsanity.com/paper/2311.00346/) (2023)
- [Fast White-Box Adversarial Streaming Without a Random Oracle](https://mlsanity.com/paper/2406.06808/) (2024)
- [The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimation](https://mlsanity.com/paper/2507.16345/) (2025)
- [Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming](https://mlsanity.com/paper/2509.16915/) (2025)

## 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.