On Sample-Based Testers

Webpage for a paper by Oded Goldreich and Dana Ron


The standard definition of property testing endows the tester with the ability to make arbitrary queries to ``elements'' of the tested object. In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object. While sample-based testers were defined by Goldreich, Goldwasser, and Ron ({\em JACM}\/ 1998), most research in property testing is focused on query-based testers.

In this work, we advance the study of sample-based property testers by providing several general positive results as well as by revealing relations between variants of this testing model. In particular:

While most of this work ignores the time complexity of testing, one part of it does focus on this aspect. The main result in this part is a sublinear-time sample-based tester for $k$-Colorability, for any $k\geq2$.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.