ECCC-Report TR07-057https://eccc.weizmann.ac.il/report/2007/057Comments and Revisions published for TR07-057en-usFri, 13 Jul 2007 00:00:00 +0300
Revision 1
| On the Average-Case Complexity of Property Testing |
Oded Goldreich,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2007/057#revision1Motivated 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.
Fri, 13 Jul 2007 00:00:00 +0300https://eccc.weizmann.ac.il/report/2007/057#revision1
Paper TR07-057
| On the Average-Case Complexity of Property Testing |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2007/057Motivated 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.
Wed, 11 Jul 2007 11:43:33 +0300https://eccc.weizmann.ac.il/report/2007/057