[Colloq] ROOM CHANGE: 366 WVH, TODAY, December 6, Ronitt Rubinfeld

[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
366 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

_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq