On the Average-Case Complexity of Property Testing
Webpage for a paper by Oded Goldreich
Motivated by a recent study of Zimand (22nd CCC, 2007),
we consider the average-case complexity of property testing
(focusing, for clarity, on testing properties of Boolean strings).
We make two observations:
We also present a natural example for which the approach of Item~2
is inapplicable, while Zimand's approach may be applicable.
- In the context of average-case analysis with respect to
the uniform distribution (on all strings of a fixed length),
property testing is trivial. Specifically,
either the yes-instances (i.e., instances having the property)
or the no-instances (i.e., instances that are far from having the property)
are exponentially rare, and thus the tester
may just reject (resp., accept) obliviously of the input.
- Turning to average-case derandomization with respect to
distributions that assigns noticeable probability mass to
both yes-instances and no-instances, we identify a natural
class of distributions and testers for which
average-case derandomization results can be
obtained directly (i.e., without using randomness extractors).
Furthermore, the resulting deterministic algorithm may preserve
the non-adaptivity of the original tester.
(In contrast, Zimand's argument utilizes a strong type
of randomness extractors and introduces adaptivity
into the testing process.)
Material available on-line
- First version posted (here):
- Revisions: none yet.
either Oded Goldreich's homepage.
or general list of papers.