The Power of Randomness in Computation

Abstract

Randomness is a powerful resource in computation. As we will see, randomness can be used to save time, space, or communication, and provide new ways for doing mathematical proofs. However, randomized algorithms typically depend on the availability of a perfect random source, whose existence even in nature is debatable. We will see how to deal with this issue, using randomness extractors and pseudo-random generators.