Theory Day March 2, 2009 - Ronitt RubinfeldIn 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. |