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.
Funding Information
  • Israel Science Foundation (1595/19, 993/17 and 1871/19)
  • Blavatnik Family Foundation
  • European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (882396)