Wednesday, October 12, 2016 - 4:00pm to 5:00pm

Speaker:

Ilias Diakonikolas

Biography:

USC

Seminar group:

We study problems in distribution property testing: Given sample access to one or more unknown discrete distributions, we want to determine whether they have some global property or are

Using our framework, we obtain optimal estimators for a wide variety of

As our second main contribution, we provide a direct general approach for proving distribution testing lower bounds, by bounding the mutual information. Our lower bound approach is not restricted to symmetric properties, and we use it to prove tight lower bounds for all the aforementioned problems.

Joint work with Daniel Kane.