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.