A Strong Separation for Adversarially Robust $\ell_0$ Estimation for
Linear Sketches
A Strong Separation for Adversarially Robust $\ell_0$ Estimation for
Linear Sketches
The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions that is fixed in advance. However, many real-world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing …