Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utcsrgv.UUCP
Path: utzoo!utcsrgv!phyllis
From: phyllis@utcsrgv.UUCP (Phyllis Eve Bregman)
Newsgroups: ont.events
Subject: UofT DCS Seminar Schedule for week of Dec. 12th
Message-ID: <2912@utcsrgv.UUCP>
Date: Fri, 9-Dec-83 14:48:10 EST
Article-I.D.: utcsrgv.2912
Posted: Fri Dec  9 14:48:10 1983
Date-Received: Fri, 9-Dec-83 17:45:12 EST
Organization: CSRG, University of Toronto
Lines: 21

      UofT Department of Computer Science Seminar Schedule for
                the week of December 12th 1983
		
Thursday, December 15th, 2:00 P.M., GB248:  Mr. Silvio Micali,
   Laboratory for Computer Science, Cambridge, Mass.:  "How to
   construct random functions".

   ABSTRACT:  We assume that functions that are one-way in a very
   weak sense exist.  We prove that in probabilistic polynomial
   time it is possible to construct **deterministic** polynomial
   time computable functions g: {1,...,2 sup k} ---> {1,...2 sup k}
   that cannot be distinguished from a **random** function by any
   polynomial time algorithm.

   This complexity theoretic result has many applications to
   probabilistic constructions, cryptography, protocols, hashing
   and counting arguments.
-- 
		Phyllis Eve Bregman
		CSRG, Univ. of Toronto
		{decvax,linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllis