Uses of randomness in computation

Details Uses of randomness in computation Uses of randomness in computation

2010-04-19

arxiv.org/abs/1004.3108v2

Computer Science

Data Structures and Algorithms

An old Technical Report, not published elsewhere. 14 pages. For further details see http://wwwmaths.anu.edu.au/~brent/pub/pub1

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Uses of randomness in computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Uses of randomness in computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uses of randomness in computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-59313