# Adversarially Robust Streaming via Dense--Sparse Trade-offs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2021.

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

- [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)

## Abstract (arXiv)

A streaming algorithm is adversarially robust if it is guaranteed to perform correctly even in the presence of an adaptive adversary. Recently, several sophisticated frameworks for robustification of classical streaming algorithms have been developed. One of the main open questions in this area is whether efficient adversarially robust algorithms exist for moment estimation problems under the turnstile streaming model, where both insertions and deletions are allowed. So far, the best known space complexity for streams of length m, achieved using differential privacy (DP) based techniques, is of order tildeO(m1/2) for computing a constant-factor approximation with high constant probability. In this work, we propose a new simple approach to tracking moments by alternating between two different regimes: a sparse regime, in which we can explicitly maintain the current frequency vector and use standard sparse recovery techniques, and a dense regime, in which we make use of existing DP-based robustification frameworks. The results obtained using our technique break the previous m1/2 barrier for any fixed p. More specifically, our space complexity for F2-estimation is tildeO(m2/5) and for F0-estimation, i.e., counting the number of distinct elements, it is tilde O(m1/3). All existing robustness frameworks have their space complexity depend multiplicatively on a parameter λ called the flip number of the streaming problem, where λ = m in turnstile moment estimation. The best known dependence in these frameworks (for constant factor approximation) is of order tildeO(λ1/2), and it is known to be tight for certain problems. Again, our approach breaks this barrier, achieving a dependence of order tildeO(λ1/2 - c(p)) for Fp-estimation, where c(p) > 0 depends only on p.