# Adversarially Robust Streaming Algorithms via Differential Privacy

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2020.

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

- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)
- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023)
- [Hot PATE: Private Aggregation of Distributions for Diverse Task](https://mlsanity.com/paper/2312.02132/) (2023)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Smoothed Differential Privacy](https://mlsanity.com/paper/2107.01559/) (2021)
- [Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise](https://mlsanity.com/paper/2407.20068/) (2024)
- [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)

A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary. We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy. This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.