We survey several works regarding the complexity of testing various properties of distributions, given access to samples from the distributions. Such properties include (1) testing if two distributions have small statistical distance, (2) testing if the marginal distributions induced by a joint distribution are independent, and (3) approximating the entropy of the distribution. It is easy to show naive algorithms which have sample complexities that are at least linear in the size of the support of the underlying discrete probability distributions. However, we are interested in algorithms whose sample complexity is *sublinear* in the size of the support. Recently such algorithms were shown for all of the above problems. Furthermore, for the first two problems, there are lower bounds that show that the sample complexity of the algorithms are tight to within polylogarithmic factors.

Many of the results described in this talk are contained in the following:

Goldreich, O., Ron, D., ``On Testing Expansion in Bounded-Degree Graphs'',

Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P., ``Testing the closeness of distributions'', Proc. 41st IEEE Conference on Foundations of Computer Science, 2000.

Batu, T., Fischer, E., Fortnow, L., Kumar, R., Rubinfeld, R., White, P., ``Testing random variables for independence and identity'', Proc. 42nd IEEE Conference on Foundations of Computer Science, 2001.

Batu, T., Dasgupta, S., Kumar, R., Rubinfeld, R., ``The complexity of approximating the entropy''. To appear in STOC 2002 and Computational Complexity 2002.