A Strong Separation for Adversarially Robust ${\ell }_0$ Estimation for Linear Sketches

Elena Gribelyuk, Honghao Lin, David P. Woodruff +2

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 advan…