Testing Independence Properties of Distributions

Several recent works have shown how to quickly test
various global properties of distributions, when given access to only
a few samples from the distributions.  We focus on properties
that give an indication of various limited independence measures
of an underlying joint distribution.  We describe algorithms whose sample
complexities are *sublinear* in the size of the support for many 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.

Joint work with  Alon, Andoni, Kaufman, Matulef and Xie.