On Sample-Based Testers
Webpage for a paper by Oded Goldreich and Dana Ron
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$.
Material available on-line
Back to
either Oded Goldreich's homepage
or general list of papers.