Adversarially Robust Streaming Algorithms via Differential Privacy

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

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2022-12, Vol.69 (6), p.1-14, Article 42
Main Authors: Hassidim, Avinatan, Kaplan, Haim, Mansour, Yishay, Matias, Yossi, Stemmer, Uri
Format: Article
Language:English
Subjects:
Algorithms
Data transmission
Privacy
Robustness
Streaming models
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0004-5411
1557-735X
DOI:10.1145/3556972