Property Testing and its connection to Learning and Approximation

Oded Goldreich, Shafi Goldwasser and Dana Ron

We consider the question of determining whether a function $f$ has property $P$ or is $epsilon$-far from any function with property $P$. A property testing algorithm is given a sample of the value of $f$ on instances drawn according to some distribution, and, in some cases, it is also allowed to query $f$ on instances of its choice.

We establish some connection between property testing and problems in learning theory. Next, we focus our attention on testing graph properties, and devise algorithms to test whether a graph has properties such as being $k$-colorable or having a $rho$-clique (clique of density $rho$ w.r.t the vertex set). Our graph property testing algorithms are probabilistic and make assertions which are correct with high probability, utilizing only $poly(1/epsilon)$ edge-queries into the graph, where $epsilon$ is the distance parameter. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph which correspond to the property being tested, if it holds for the input graph.

Versions on-line:

See also the Property Testing page.

Back to homepages of authors: Oded Goldreich, Shafi Goldwasser, Dana Ron.