  Random number generators are widely used in practical algorithms. Examples
include simulation, number theory (primality testing and integer
factorization), fault tolerance, routing, cryptography, optimization by
simulated annealing, and perfect hashing. Complexity theory usually considers
the worst-case behaviour of deterministic algorithms, but it can also consider
average-case behaviour if it is assumed that the input data is drawn randomly
from a given distribution. Rabin popularised the idea of "probabilistic"
algorithms, where randomness is incorporated into the algorithm instead of
being assumed in the input data. Yao showed that there is a close connection
between the complexity of probabilistic algorithms and the average-case
complexity of deterministic algorithms. We give examples of the uses of
randomness in computation, discuss the contributions of Rabin, Yao and others,
and mention some open questions. This is the text of an invited talk presented
at "Theory Day", University of NSW, Sydney, 22 April 1994.
