The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ${\ell }_2$ Norm Estimation

Sara Ahmadian, Edith Cohen, Uri Stemmer

Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the black-box adversarial se…