mlsanityData to 7 Oct 2026

Adversarially Robust Streaming Algorithms via Differential Privacy

arXiv 2004.05975 ↗First posted 13 Apr 2020cs.DS cs.LGcited by 21

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 5; 2023: 6; 2024: 3; 2025: 2.

21 papers.

Sort:

By area:

  1. 2021Adaptive Machine Unlearningcited by 164
  2. 2021Adversarial Laws of Large Numbers and Optimal Regret in Online Classificationcited by 39
  3. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  4. 2021Adversarial Robustness of Streaming Algorithms through Importance Samplingcited by 13
  5. 2021A Framework for Adversarial Streaming via Differential Privacy and Difference Estimatorscited by 9
  6. 2022Adaptive Data Analysis with Correlated Observationscited by 9
  7. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 7
  8. 2023Unbounded Differentially Private Quantile and Maximum Estimationcited by 6
  9. 2022On the Robustness of CountSketch to Adaptive Inputscited by 5
  10. 2023Streaming Algorithms for Learning with Experts: Deterministic Versus Robustcited by 3
  11. 2023Hot PATE: Private Aggregation of Distributions for Diverse Taskcited by 3
  12. 2024Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysiscited by 3
9 more
  1. 2022The Complexity of Dynamic Least-Squares Regressioncited by 2
  2. 2022Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputscited by 2
  3. 2021Smoothed Differential Privacycited by 1
  4. 2023Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Modelcited by 0
  5. 2023Adversarially Robust Distributed Count Tracking via Partial Differential Privacycited by 0
  6. 2024Fast White-Box Adversarial Streaming Without a Random Oraclecited by 0
  7. 2024Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noisecited 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