voula@utcsri.UUCP (Voula Vanneli) (02/20/85)
University of Toronto
Department of Computer Science
(RW = Ramsey Wright Building, 25 Harbord Street)
THEORETICAL ASPECTS SEMINAR - Wednesday, February 27, 11
a.m., RW 117
Umesh Vazirani
University of California at Berkeley
"Quasi-Random Sequences from Two Communicating Slightly-Random Sources"
Abstract
Random sequences of bits are fundamental to several computa-
tional applications. However, physical sources of random
noise are at best imperfect. Santha & Vazirani proposed a
very general model for such sources of random noise - the
Slightly-Random Source.
We show how to use two slightly-random sources to produce
quasi-random sequences. Such sequences can be provably used
in place of truly random sequences in computational applica-
tions. Whereas our algorithm for generating these sequences
is simple and easily implementable, the proof is based on a
delicate argument involving a potential function.
University of Toronto
Department of Computer Science
(SF = Sandford Fleming Building, 10 King's College Road)
THEORETICAL ASPECTS SEMINAR - Thursday, February 28, 4 p.m.,
SF 1105
Professor Charles Leiserson
Laboratory for Computer Science, M.I.T.
"Fat-Trees; Universal Networks for Hardware-Efficient Supercomputing"