Another motivation for reducing the randomness complexity of algorithms

Webpage for a paper by Oded Goldreich


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.

Material available on-line


Back to either Oded Goldreich's homepage. or general list of papers.