On Sample-Based Testers
Oded Goldreich, Dana Ron · 2015
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 JACM 1998), with few exceptions, most research in property testing is focused on query-based testers.