Doctoral Speaking Skills Talk - Honghao Lin

— 2:00pm

Location:
In Person - Newell-Simon 3305

Speaker:
HONGHAO LIN, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://honghlin.github.io/

A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches

The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions that is fixed in advance. However, many real-world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model.

In this talk, we will give the first known adaptive attack against linear sketches for the well-studied $\ell_0$-estimation problem over turnstile, integer streams. For any linear streaming algorithm 𝒜 that uses sketching matrix $\mathbf{A}\in \mathbb{Z}^{r \times n}$ where $n$ is the size of the universe, this attack makes $\tilde{O}(r^8)$ queries and succeeds with high constant probability in breaking the sketch. We will also give an adaptive attack against linear sketches for the $\ell_0$-estimation problem over finite fields $\mathbb{F}_p$, which requires a smaller number of $\tilde{O}(r^3)$ queries. 

Finally, we will provide an adaptive attack over $\mathbb{R}^n$ against linear sketches $\mathbf{A} \in \mathbb{R}^{r \times n}$ for $\ell_0$-estimation, in the setting where $\mathbf{A}$ has all nonzero subdeterminants at least $\frac{1}{\text{poly}(r)}$. Our results provide an exponential improvement over the previous number of queries known to break an $\ell_0$-estimation sketch.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

Add event to Google
Add event to iCal