Adversarially Robust Streaming Algorithms
summary
Shows that classic linear sketches fail against adaptive streams and gives concrete remedies: maintain multiple black‑box copies and sketch switching based on a problem’s flip number (number of 1+ε jumps), e.g., F0 in insertion‑only has flip ≈ log n/ε, so overhead is modest; a differential privacy framework cuts that overhead to ~√(flip) using sparse vector and private median; sampling methods remain robust via Littlestone dimension; major open gap remains: robust F0/F2 still require exponentially more space than static.
AI-written summary · about
chapters (14)
- 0:00Adversarially robust streaming intro
- 1:06Streaming algorithms basics
- 10:31Linear sketching vs adversaries
- 14:31Making algorithms robust
- 27:50Sketch switching framework
- 36:07Beyond flip number robustness
- 41:07Sampling-based robustness
- 45:49Sketching vs sampling
- 48:01Graph coloring challenges
- 49:27White box vs black box
- 50:54Connections to research
- 53:34Field history insights
- 57:40Open questions
- 1:00:54Q&A
related talks
26mA Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
33mError Correction for Streaming Messages
50mRobustness of Sketches to Adaptive nputs
18mDifferentially Private Continual Releases of Streaming Frequency Moment Estimations
30mA Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches
44mHow Robust are Linear Sketches to Adaptive Inputs?
47mA Blackbox Reduction for Adaptive Adversaries using Differential Privacy
43mDifferential Privacy Meets Robust Statistics