EP06-001
Authors: Oded Goldreich
Contact: oded.goldreich"at"weizmann.ac.il
Keywords: Randomness Complexity, Weak Sources of Randomness, Randomness Extractors, Pseudorandom Generators, Sampling, Property Testing.

Abstract:
We observe that the randomness-complexity of an algorithm effects the time-complexity of implementing a version of it that utilizes a weak source of randomness (through a randomness-extractor). This provides an additional motivation for the study of the randomness complexity of randomized algorithms. We note that this motivation applies especially in the case that derandomization is prohibitingly costly.