Talk By Ilya Mironov (Google Brain)
summary
Defines the Adversarial Sketch Model where edge devices share no secret, shows equality testing suffers a quadratic lower bound on sketch size via reductions from the Simultaneous Message Model, and notes linear sketches fail against adaptive queries (Hardt & Woodruff negative result). Offers workarounds: a multiscale code construction that weights Hamming distances to reduce updates, an insertion-only failure-structure scheme using burner sketches (logarithmic number), and a remedy using the sparse vector technique to privately select medians of sketches.
AI-written summary · about
chapters (12)
- 0:00Sublinear algorithms intro
- 1:27Adversarial sketch model
- 5:40Equality testing in adversarial
- 8:16Lower bounds via SMM
- 12:48Weighted distances breakthrough
- 14:13Robust data structures
- 16:02Early sketching lessons
- 18:38Adaptive inputs and sketches
- 19:47Multiplicative approximation
- 21:13Privacy for adversarial sketches
- 22:42Future directions
- 23:46Q&A
related talks
57mA Simple Quantum Sketch With Applications to Graph Algorithms
10mSelf-interpreting Adversarial Images
39mTrust Cards For AI
01h 07mDiscussion Session
01h 05mAdaptive Generalization: The Role of Dynamic Evaluation in Low-Resource Settings
41mEnhancing LLMs with Graph Technology
01h 04mRobust Generalization in the Era of LLMs: Jailbreaking Attacks and Defenses
42mHow to attack AI systems (and how to defend them) !!!!