marina@ai.toronto.edu (Marina Haloulos) (10/18/89)
Department of Computer Science, University of Toronto
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
THEORY SEMINAR
GB119, at 3:00 p.m., Thursday 26 October 1989
Dr. Rene Peralta
Univ. of Wisconsin, Milwaukee
"On the randomness complexity of algorithms"
A Probabilistic Turing Machine uses three scarce resources: time, space,
and randomness. Computational problems are usually classified according to
the amount of time or space necessary for their solution with exponentially
low probability of error or failure. Given a computational problem, there
are several ways to pose the question "how much randomness is needed to
solve this problem?". Our approach is to restrict computations to
polynomial-time and bound the error probability by $(1/2) sup n$ on all
inputs of size $n$. We then ask "how many random bits are necessary and/or
sufficient to solve this problem within these parameters"? From this point
of view, we investigate the amount of randomness needed for primality
testing, computation of square roots modulo a prime number, and finding
quadratic non-residues modulo a prime number.