Speaker: |
Anindya De (University of Pennsylvania United States) |

Organiser: |
Piyush Srivastava |

Date: |
Monday, 6 Jan 2020, 10:30 to 11:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

In this talk, we look at this question from the vantage point of property testing and study the decision variant of the following question -- namely, what is the complexity of deciding if the unknown vector w is k-sparse (or at least say 0.01 far from k-sparse in \ell_2 distance). We show that the decision version of the problem can be solved with samples which are independent of n as long as the background distribution D is i.i.d. and the components are not Gaussian. We further show that weakening any of the conditions in this result necessarily makes the complexity scale as log n (thus showing our results are tight).

Joint work with Xue Chen (Northwestern) and Rocco Servedio (Columbia).