On the randomness complexity of property testing
Webpage for a paper by Oded Goldreich and Or Sheffet
Abstract
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 motivation 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.
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.