Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-109 | 6th October 2013 19:25

On Sample-Based Testers

RSS-Feed




Revision #1
Authors: Oded Goldreich, Dana Ron
Accepted on: 6th October 2013 19:25
Downloads: 899
Keywords: 


Abstract:

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:

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 this
part is a sublinear-time sample-based tester for $k$-Colorability, for any $k\geq2$.



Changes to previous version:

Added an appendix (A.2) that relates various notions of sampling.


Paper:

TR13-109 | 11th August 2013 19:59

On Sample-Based Testers





TR13-109
Authors: Oded Goldreich, Dana Ron
Publication: 11th August 2013 20:00
Downloads: 1206
Keywords: 


Abstract:

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:

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 this
part is a sublinear-time sample-based tester for $k$-Colorability, for any $k\geq2$.



ISSN 1433-8092 | Imprint