• Calendar

January 25, Tuesday
12:00 – 14:00

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.

Bio:

Sofya recieved her Ph.D. from MIT in 2003. Last year she was a post-doc at the Hebrew University of Jerusalem, supported by the Lady Davis Fellowship. Currently she is a post-doc at the Weizmann Institute of Science.