A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=zI0FPRUaGt8


Duration: 0:00
81 views
2

Samson Zhou (Texas A&M University)
https://simons.berkeley.edu/talks/samson-zhou-texas-am-university-2024-08-07
Workshop on Local Algorithms (WoLA)

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.



Other Videos By Simons Institute for the Theory of Computing


2024-11-12Transfer learning via local convergence rates of the nonparametric least squares estimator
2024-11-12Transfer learning for weak-to-strong generalization
2024-11-12User-level and federated local differential privacy
2024-11-11The Evolution of Domain Transfer in the Era of Pre-trained Language Models
2024-11-11Label Noise: Ignorance is Bliss
2024-11-11The Data Addition Dilemma
2024-11-11Pseudo-Labeling for Covariate Shift Adaptation
2024-11-11How Transformers Learn Causal Structure with Gradient Descent
2024-10-16The Enigma of LLMs: on Creativity, Compositionality, Pluralism, and Paradoxes
2024-10-02Let’s Try and Be More Tolerant: On Tolerant Property Testing and Distance Approximation
2024-10-02A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches
2024-10-02Towards Practical Distribution Testing
2024-10-02Toward Optimal Semi-streaming Algorithm for (1+ε)-approximate Maximum Matching
2024-10-02Plenary Talk: Privately Evaluating Untrusted Black-Box Functions
2024-10-02The long path to \sqrt{d} monotonicity testers
2024-10-02O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set
2024-10-02Distribution Learning Meets Graph Structure Sampling
2024-10-02On the instance optimality of detecting collisions and subgraphs
2024-10-02Low Degree Testing over the Reals
2024-10-02Talk By Tal Herman
2024-10-02Verifiable Data Science via Interactive Proofs