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 byGoldreich, 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:

We show that certain types of query-based testers yield sample-based testers of sublinear sample complexity.For example, this holds for a natural class of proximity oblivious testers.We study the relation between distribution-free sample-based testers and one-sided error sample-based testers w.r.t the uniform distribution.

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