NeurIPS 2020oral64 citations
Adversarially Robust Streaming Algorithms via Differential Privacy
Avinatan Hasidim, Haim Kaplan, Yishay Mansour, Yossi Matias, Uri Stemmer
Abstract
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.
BibTeX
@inproceedings{NEURIPS2020_0172d289,
author = {Hasidim, Avinatan and Kaplan, Haim and Mansour, Yishay and Matias, Yossi and Stemmer, Uri},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {147--158},
publisher = {Curran Associates, Inc.},
title = {Adversarially Robust Streaming Algorithms via Differential Privacy},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/0172d289da48c48de8c5ebf3de9f7ee1-Paper.pdf},
volume = {33},
year = {2020}
}