On the Average-Case Complexity of Property Testing

Webpage for a paper by Oded Goldreich

Abstract

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:

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.)

We also present a natural example for which the approach of Item~2 is inapplicable, while Zimand's approach may be applicable.

Material available on-line

First version posted (here): July 2007.
Revisions: none yet.

Back to either Oded Goldreich's homepage. or general list of papers.