## Uses of randomness in computation

147. R. P. Brent,
* Uses of randomness in computation*,
Technical Report TR-CS-94-06,
CSL, ANU, June 1994, 14 pp.
arXiv:1004.3108v2
Report:
dvi (24K),
pdf (200K),
ps (88K).

Transparencies (1 per page):
dvi (22K),
pdf (103K),
ps (77K).

Transparencies (4 per page):
pdf (212K).

## Abstract

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.

## Comments

This is the text of an invited talk presented at
"Theory Day", University of NSW, 22 April 1994
(also seminars at ANU and Griffith University, May 1994).
Go to next publication

Return to Richard Brent's index page