Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!neat.cs.toronto.edu!marina
From: marina@ai.toronto.edu (Marina Haloulos)
Newsgroups: ont.events
Subject: Dr. Rene Peralta, Thursday 26 October 1989: THEORY SEMINAR
Message-ID: <89Oct17.132227edt.3613@neat.cs.toronto.edu>
Date: 17 Oct 89 17:23:27 GMT
Lines: 26


           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.