The Usefulness of Randomization in Computation.

This paper surveys three topics connected with the use of randomization in computation. The first is the construction and use of pseudorandom numbers in place of truly "random" numbers. The second concerns situations in which randomized computations offer speedup over deterministic computation. The third topic concerns the use of randomized algorithms to achieve privacy and authentication. This paper will form part of a report, "Probability on Algorithms," in preparation by the Committee on Applied and Theoretical Statistics (CATS) of the National Research Council.