Lecture Notes on Property Testing

Oded Goldreich

These lecture notes serve as a basis for a forthcoming book, titled introduction to property testing.

These notes are not updated; better versions are available as part of the full text posted HERE.

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).

These lecture notes will be written towards teaching an introductory course on the subject (in Fall 2015). Specific topics to be covered will include:

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

Two specific texts that were converted (and extended) into the foregoing lecture notes are --

Hence, these survers are superseeded by the lecture notes.

Back to homepage.