ECCC-Report TR01-008https://eccc.weizmann.ac.il/report/2001/008Comments and Revisions published for TR01-008en-usWed, 10 Jan 2001 16:00:27 +0200
Paper TR01-008
| On the strength of comparisons in property testing |
Eldar Fischer
https://eccc.weizmann.ac.il/report/2001/008An $\epsilon$-test for a property $P$ of functions from
${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized
algorithm, which makes queries on the value of an input function at
specified locations, and distinguishes with high probability between the
case of the function satisfying $P$, and the case that it has to be
modified in more than $\epsilon d$ places to make it satisfy $P$.
We prove that an $\epsilon$-test for any property defined in terms of the
order relation, such as the property of being a monotone nondecreasing
sequence, cannot perform less queries (in the worst case) than the best
$\epsilon$-test which uses only comparisons between the queried values. In
particular, we show that an adaptive algorithm for testing that a sequence
is monotone nondecreasing performs no better than the best non-adaptive
one, with respect to query complexity. From this follows a tight lower
bound on tests for this property.
Wed, 10 Jan 2001 16:00:27 +0200https://eccc.weizmann.ac.il/report/2001/008