Adversarially Robust Streaming via Dense--Sparse Trade-offs

Understand

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 $\tilde{O}(m^{1/2})$ for computing a constant-factor approximation with high constant probability.