A Strong Separation for Adversarially Robust ℓ₀ 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 which 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 the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model. In this work, we give the first known adaptive attack against linear sketches for the well-studied <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{0}$</tex>-estimation problem over turnstile, integer streams. For any linear streaming algorithm <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{A}$</tex> which uses sketching matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{A}\varepsilon \mathbb{Z}^{r\times n}$</tex>, this attack makes <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{\mathcal{O}}(r^{8})$</tex> queries and succeeds with high constant probability in breaking the sketch. Additionally, we give an adaptive attack against linear sketches for the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{0}$</tex>-estimation problem over finite fields <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{p}$</tex>, which requires a smaller number of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{\mathcal{O}}(r^{3})$</tex> queries. Finally, we provide an adaptive attack over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{R}^{n}$</tex> against linear sketches A <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\in \mathbb{R}^{r\times \mathfrak{n}}$</tex> for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{0}$</tex>-estimation, in the setting where A has all nonzero subdeterminants at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\frac{1}{\text{poly}(r)}$</tex>. Our results provide an exponential improvement over the previous number of queries known to break an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{0}$</tex>-estimation sketch.