[Colloquium] Raskhodnikova talk today 2:30 at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK 

Speaker: Sofya Raskhodnikova
The Hebrew University of Jerusalem, Israel 

Speaker’s homepage: http://theory.lcs.mit.edu/~sofya/

Time: 2:30pm
Date: Tuesday, March 2nd
Place: TTI-C (1427 E. 60th - U of C Press Building)
Refreshments provided 

Title: What we can (and cannot) test with a sublinear number of samples 

Abstract: 
Suppose we are given a list of numbers and we wish to determine whether it is
sorted. That problem obviously requires reading the entire list. But Ergun,
Kannan, Kumar, Rubinfeld and Viswanathan showed in 1998 that if we know in
advance that our list is either sorted or far from sorted, we can perform the
test by examining only a small portion of the list. Sorting is thus an example
of a testable property, as defined by Rubinfeld and Sudan in 1996, where we can
distinguish between objects having the property and objects that are far from
having it by examining only a small part of the object.

We will start by defining property testing, then talk about monotonicity testing
which is a generalization of the sortedness testing problem. We will present
algorithms and lower bounds that give partial classification of properties in
terms of their query complexity, that is, the number of samples needed to test
for them. 
 
If you have questions, or would like to meet the speaker, please contact Meridel
at 4-9873 or mtrimble at tti-c.org
 
For information on future TTI-C talks or events, please go to the TTI-C Events 
page: http://www.tti-c.org/events.shtml