Abstract
We give the first known adaptive attack against linear sketches for the well-studied L_0-estimation problem over turnstile, integer streams. For any linear streaming algorithm A that uses a sketching matrix of dimension r by n, this attack makes ~O(r^8) queries and succeeds with high constant probability in breaking the sketch.
Joint work with Elena Gribelyuk, Honghao Lin, David P. Woodruff, and Huacheng Yu.