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.
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:
- Testing graph properties (in the adjacency matrix model,
the bounded-degree model, and the general graph model);
- Testing algebraic properties (linearity and low-degree polynomials);
- Testing properties of Boolean functions (monotonicity and dictatorship);
- Testing properties of distributions (e.g., identity);
- Proximity-oblivious testers, tolerant testers,
sample-based testers, distribution-free testers,
and proofs of proximity.
- Local computation:
parameter estimation, finding huge structures, and reconstruction.
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.