Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-057 | 13th July 2007 00:00

On the Average-Case Complexity of Property Testing

RSS-Feed




Revision #1
Authors: Oded Goldreich, Oded Goldreich
Accepted on: 13th July 2007 00:00
Downloads: 1463
Keywords: 


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


Paper:

TR07-057 | 11th July 2007 00:00

On the Average-Case Complexity of Property Testing





TR07-057
Authors: Oded Goldreich
Publication: 11th July 2007 11:43
Downloads: 1557
Keywords: 


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.



ISSN 1433-8092 | Imprint