[Colloq] Ronitt Rubinfeld, Wedneaday, December 6, 110WVH

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Ronitt Rubinfeld
MIT

Who will speak on:
Testing Global Properties of Distributions

Wednesday, December 6, 2006
12:00pm
110 West Village H
Northeastern University

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.

Host: Ravi Sundaram