Revision #1 Authors: Oded Goldreich, Oded Goldreich

Accepted on: 13th July 2007 00:00

Downloads: 1512

Keywords:

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:

<ol>

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

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

</ol>

We also present a natural example for which the approach of Item~2

is inapplicable, while Zimand's approach may be applicable.

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.