Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site utcsri.UUCP
Path: utzoo!utcsri!voula
From: voula@utcsri.UUCP (Voula Vanneli)
Newsgroups: ont.events
Subject: Theoretical Aspects Seminars
Message-ID: <788@utcsri.UUCP>
Date: Wed, 20-Feb-85 15:03:46 EST
Article-I.D.: utcsri.788
Posted: Wed Feb 20 15:03:46 1985
Date-Received: Wed, 20-Feb-85 18:44:51 EST
Distribution: ont
Organization: CSRI, University of Toronto
Lines: 41


                   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"