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

Some of 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:

- A first lecture: themes, notions, definitions, and goals.
- Testing algebraic properties:
- Testing properties of functions over product domains:
- monotonicity
- properties of Boolean functions such as dictatorship, juntas, and monomials,
- and testing by implicit sampling;

- lower bound techniques
- Testing graph properties
- in the adjacency matrix (a.k.a dense graph) model,
- in the bounded-degree graph model,
- and in the general graph model;

- Testing properties of distributions
- Add'l topics: Tolerant testers, sample-based testers, distribution-free testers, local computation algorithms (i.e., finding huge structures and reconstruction), and MAPs.
- Locally testable codes and proofs (an overview).
- Appendix: some probabilistic preliminaries

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

- Short Locally Testable Codes and Proofs - A Survey in Two Parts .
- Introduction to Testing Graph Properties

Back to homepage.