Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-015 | 1st March 2007 00:00

On the randomness complexity of property testing



We initiate a general study of the randomness complexity of
property testing, aimed at reducing the randomness complexity of
testers without (significantly) increasing their query complexity.
One concrete motovation for this study is provided by the
observation that the product of the randomness and query complexity
of a tester determine the actual query complexity of implementing
a version of this tester that utilizes a weak source of randomness
(through a randomness-extractor).
We present rather generic upper- and lower-bounds on the
randomness complexity of property testing and study in depth
the special case of testing bipartiteness in two standard
property testing models.

ISSN 1433-8092 | Imprint