Theory Day March 2, 2009 - Ronitt Rubinfeld


In what kind of shape is your distribution?

Abstract:
We survey several works regarding the complexity of testing
various global properties of distributions, when given access to only
a few samples from the distributions. We will focus on properties
that give some indication of the ``shape'' of the underlying
distribution -- for example, is the distribution monotone, or uniform over a small subset? We will describe algorithms whose sample
complexities are *sublinear* in the size of the support for such
testing problems. In contrast, classical techniques, such as the
Chi-squared test or the straightforward use of Chernoff bounds,
have sample complexities that are at least linear in the size
of the support of the underlying discrete probability distributions.