BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/897
DTSTAMP:20230914T125942Z
SUMMARY:Pseudo-deterministic Algorithms
DESCRIPTION:Speaker: Vishwas Bhargava (Rutgers University\nNew Brunswick-Pi
scataway\nNew Jersey\nUnited States)\n\nAbstract: \nIn this talk\, we desc
ribe a new type of probabilistic algorithm (introduced by Gat and Goldwass
er [GG11]) called Pseudo-deterministic Algorithms: a randomized algorithm
which is guaranteed to run in expected polynomial time and to produce a c
orrect and unique solution with high probability.\nThe name comes from the
fact that they can not be distinguished from deterministic algorithms in
polynomial time by a probabilistic polynomial time observer with black-bo
x access to the algorithm.\nWe will discuss some interesting algorithms as
well as open problems. We will also look at Pseudo-deterministic Algori
thms from a complexity point of view.\n
URL:https://www.tcs.tifr.res.in/web/events/897
DTSTART;TZID=Asia/Kolkata:20180824T171500
DTEND;TZID=Asia/Kolkata:20180824T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR