BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Rothschild Lecture: Pseudo Deterministic Algorithms and Applicatio
 ns to Cryptography - Goldwasser\, S (MIT)
DTSTART:20120412T160000Z
DTEND:20120412T170000Z
UID:TALK37437@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We describe a new type of probabilistic search algorithm: \na 
 randomized algorithm which is guaranteed to run\nin expected polynomial ti
 me\, and with high probability produce correct\nand unique solution. These
  algorithms are pseudo-deterministic: they\ncan not be distinguished from 
 deterministic algorithms in polynomial\ntime by a probabilistic polynomial
  time observer with black box\naccess.\n\nWe will exhibit a necessary and 
 sufficient condition for the existence of a\n pseudo-deterministic algorit
 hm for an NP relation R.\n Several examples of such algorithms\, for probl
 ems in\nnumber theory\, algebra and graph theory which improve on determin
 istic\nsolutions\, will also be discussed. We note that the characterizati
 on\nscales up.\n\nThe notion of pseudo-deterministic \ncomputations is int
 eresting beyond just sequential polynomial time\nalgorithms\, in other dom
 ains where the use of randomization is\nessential. For example\, one can d
 efine and obtain pseudo-deterministic\nfault tolerance distributed algorit
 hms and pseudo deterministic sub-linear\nalgorithms for tasks which are im
 possible\nto solve without randomization. We will discuss several such dom
 ains.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR