Combinatorial Property Testing: Surveys and Works

Oded Goldreich


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

Most of the works mentioned below focus on combinatorial properties, and specifically on graph properties. The two standard representations of graphs - by adjacency matrix and by incidence lists - yield two different models for testing graph properties. In the first model graphs, most appropriate for dense graphs, distance between N-vertex graphs is measured as the fraction of edges on which the graphs disagree over N^2. In the second model graphs, most appropriate for bounded-degree graphs, distance between N-vertex d-degree graphs is measured as the fraction of edges on which the graphs disagree over dN. These two models are the topic of my own surveys, provided below. For a wider perspective, see Dana Ron's tutorials (below).

Surveys

For a wider perspective and more details, see See also a survey of the related topic of Short Locally Testable Codes and Proofs (by Oded Goldreich, 2004 and 2010).

My own papers in the area (in chronological order)


Back to Oded Goldreich's homepage or to the full list of papers.