mwang (04/12/83)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
COMPUTER SCIENCE COLLOQUIUM
- Wednesday, April 20, 1983.
Dr. S. Micali of The University of Toronto will speak
on ``Randomness versus Hardness''.
TIME: 3.30 PM
ROOM: MC 5158
ABSTRACT
We present a constructive notion of randomness unlike
the classical one given by Kolmogorov. Randomness can
be implied by computational intractability. We exhibit
pseudo-random number generators whose unpredictability
is based upon the assumed difficulty of factoring
integers. These programs, upon receiving as input a
short random seed, output a sequence of bits b sub-
script 0 , b subscript 1 , ... such that any effi-
cient strategy that predicts b subscript k+1 from
the first k bits more than 50 percent of the time can
be transformed into an efficient factoring algorithm.
Coffee and refreshments will be served at 3.00 PM.
Everyone is welcome.
April 12, 1983