Testing properties of distributions over big domains

Abstract: We describe an emerging research direction regarding the complexity of testing global properties of discrete distributions, when given access to only a few samples from the distribution. Such properties might include testing if two distributions have small statistical distance, testing various independence properties, testing whether a distribution has a specific shape (such as monotone decreasing, k-modal, k-histogram, monotone hazard rate,…), and approximating the entropy. We describe bounds for such testing problems whose sample complexities are sublinear in the size of the support.

Biography: Ronitt Rubinfeld is a professor in the Department of Electrical Engineering and Computer Science at MIT. Ronitt’s research interests revolve around sublinear time algorithms. Her work focuses on the question of what can be understood about data by looking at only a very small portion of it. Much of her current work concentrates on testing properties and estimating parameters of distributions over very large domains.