[ont.events] UofT DCS Seminar Schedule for week of Dec. 12th

phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (12/09/83)

      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