A Strong Separation for Adversarially Robust L0 Estimation for Linear Sketches

Explore a 30-minute conference talk by Samson Zhou from Texas A&M University on adversarially robust L_0 estimation for linear sketches. Delve into the first known adaptive attack against linear sketches for the L_0-estimation problem over turnstile, integer streams. Learn about the attack's methodology, which utilizes a sketching matrix of dimension r by n and makes approximately O(r^8) queries to break the sketch with high constant probability. Gain insights into this collaborative research effort with Elena Gribelyuk, Honghao Lin, David P. Woodruff, and Huacheng Yu, presented as part of the Workshop on Local Algorithms (WoLA) at the Simons Institute.