Events - Colloquia & Seminars

CCIS Colloquium Fall 2006

Testing Global Properties of Distributions

Speaker: Ronitt Rubinfeld

Affiliation: MIT

Date: Wednesday, December 6, 2006

Talk: 12:00 pm, 110 WVH

Abstract

Suppose you are studying the occurrence of a disease and need to uncover any salient statistical properties that might hold. For example, it would be important to know if the probability of contracting the disease decreases with distance of your house from a given nuclear plant, whether the distribution on zipcodes of patients is close to the distribution for another disease, or whether a person's likelihood of contracting it is correlated with their profession. Of course, you wish to notice such trends given as few samples as possible.

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. Such properties 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), and approximating the entropy. 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. We will describe algorithms whose sample complexities are *sublinear* in the size of the support for many such testing problems.

Biography

Ronitt Rubinfeld received her Bachelor's degree at the University of Michigan in 1985 and her Ph.D. in computer science in 1990 at the University of California at Berkeley. She held a postdoctoral research fellowship at Princeton University and DIMACS, followed by a year as a visiting research scholar at the Hebrew University in Jerusalem. She joined the Cornell University Computer Science faculty in 1992. In 1999, she accepted a position as a senior research scientist at NEC Research Laboratories in Princeton. She was a Fellow at the Radcliffe Institute for Advanced Study in Spring 2004. Later in 2004, she moved to MIT where she is currently a professor of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory.

Ronitt Rubinfeld's research interests include computational complexity theory, randomized algorithms and computational learning theory. Her current work is focused on sublinear time algorithms. She is a member of the editorial boards of the Theory of Computing Systems Journal, Information and Computation, and Algorithmica. She has been the recipient of an Office of Naval Research Young Investigator Award, a Cornell Association for Computer Science Undergraduate Faculty of the Year Award, a Cornell College of Teaching Engineering Award, a National Science Foundation Career Award, and an Alfred P. Sloan Research Fellowship.