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:

1. 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.
2. 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.

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: 1) 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. 2) 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 work is applicable.