Fetching the paper…
Reading the bibliography…
We present a streaming problem for which every adversarially-robust streaming algorithm must use polynomial space, while there exists a classical (oblivious) streaming algorithm that uses only polylogarithmic space.
Random sampling with a reservoir
J. S. Vitter · 1985
Earlier work this paper cites.
Conditionally-perfect secrecy and a provably-secure randomized cipher
U. M. Maurer · 1992
Earlier work this paper cites.
Unconditional security against memory-bounded adversaries
C. Cachin and U. Maurer · 1997
Earlier work this paper cites.
Information theoretically secure communication in the limited storage space model
Y. Aumann and M. O. Rabin · 1999
Earlier work this paper cites.
Everlasting security in the bounded storage model
Y. Aumann, Y. Z. Ding, and M. O. Rabin · 2002
Earlier work this paper cites.
Hyper-encryption and everlasting security
Y. Z. Ding and M. O. Rabin · 2002
Earlier work this paper cites.
Optimal randomizer efficiency in the bounded-storage model
S. Dziembowski and U. Maurer · 2004
Earlier work this paper cites.
Encryption against storage-bounded adversaries from on-line strong extractors
C.-J. Lu · 2004
Earlier work this paper cites.
Constructing locally computable extractors and cryptosystems in the bounded-storage model
S. P. Vadhan · 2004
Cited alongside, same era.
On everlasting security in the hybrid bounded storage model
D. Harnik and M. Naor · 2006
Cited alongside, same era.
Sketching in adversarial environments
I. Mironov, M. Naor, and G. Segev · 2011
Cited alongside, same era.
Analyzing graph structure via linear measurements
K. J. Ahn, S. Guha, and A. McGregor · 2012
Cited alongside, same era.
Graph sketches: sparsification, spanners, and subgraphs
K. J. Ahn, S. Guha, and A. McGregor · 2012
Cited alongside, same era.
Recovering simple signals
A. C. Gilbert, B. Hemenway, A. Rudra, M. J. Strauss, and M. Wootters · 2012
Cited alongside, same era.
Preventing false discovery in interactive data analysis is hard
M. Hardt and J. Ullman · 2014
Later among the works it cites.
Generalization in adaptive data analysis and holdout reuse
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth · 2015
Later among the works it cites.
Interactive fingerprinting codes and the hardness of preventing false discovery
T. Steinke and J. Ullman · 2015
Later among the works it cites.
The limits of post-selection generalization
K. Nissim, A. D. Smith, T. Steinke, U. Stemmer, and J. Ullman · 2018
Later among the works it cites.
The adversarial robustness of sampling
O. Ben-Eliezer and E. Yogev · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Reusable low-error compressive sampling schemes through privacy
A. C. Gilbert, B. Hemenway, M. J. Strauss, D. P. Woodruff, and M. Wootters · 2012
Cited alongside, same era.
How robust are linear sketches to adaptive inputs?
M. Hardt and D. P. Woodruff · 2013
Cited alongside, same era.
O. Ben-Eliezer, R. Jayaram, D. P. Woodruff, and E. Yogev · 2020
Later among the works it cites.
Adversarially robust streaming algorithms via differential privacy
A. Hassidim, H. Kaplan, Y. Mansour, Y. Matias, and U. Stemmer · 2020
Later among the works it cites.
Tight bounds for adversarially robust streams and sliding windows via difference estimators
D. P. Woodruff and S. Zhou · 2020
Later among the works it cites.