Introduction to Property Testing (a one-semester course)

Oded Goldreich


Introduction to Property Testing
To be given in Fall 2015

In a nutshell, Property Testing means approximate decisions performed based on a partial view of the input.

Administartion

This course will be based on weekly lectures, taking place on Tuesday 15:15-17:00 in Ziskind Room 1.
The first lecture will take place on October 27th 2015.

Those interested in attending should join the following Google Group.

Group for the Introduction to Property Testing (Fall 2015)
Enter your email:
Visit this group

Teaching Assistant: Tom Gur

Syllabus

Property Testing is concerned with approximate decisions, where the task is distinguishing between objects having a predetermined property and objects that are ``far'' from having this property. Typically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. We consider (randomized) algorithms that may query the function at arguments of their choice, and seek algorithms of very low complexity (i.e., much lower than the size of the function's domain).

Specific topics will include:

Lecture notes will be posted HERE.

Related surveys can be found in the collection Property Testing: Current Research and Surveys (Springer, LNCS 6390, 2010).


Back to homepage.