Randomized Algorithm - Derandomization

Derandomization

Randomness can be viewed as a resource, like space and time. Derandomization is then the process of removing randomness (or using as little of it as possible). From the viewpoint of computational complexity, derandomizing an efficient randomized algorithm is the question, is P = BPP ?

There are also specific methods that can be employed to derandomize particular randomized algorithms:

• the method of conditional probabilities, and its generalization, pessimistic estimators
• discrepancy theory (which is used to derandomize geometric algorithms)
• the exploitation of limited independence in the random variables used by the algorithm, such as the pairwise independence used in universal hashing
• the use of expander graphs (or dispersers in general) to amplify a limited amount of initial randomness (this last approach is also referred to as generating pseudorandom bits from a random source, and leads to the related topic of pseudorandomness)