School of Technology and Computer Science Seminars
Pseudo-deterministic Algorithms
by Vishwas Bhargava (Rutgers University, United States)
Friday, August 24, 2018
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
In this talk, we describe a new type of probabilistic algorithm (introduced by Gat and Goldwasser [GG11]) called Pseudo-deterministic Algorithms: a randomized algorithm which is guaranteed to run in expected polynomial time and to produce a correct and unique solution with high probability. The 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-box access to the algorithm. We will discuss some interesting algorithms as well as open problems. We will also look at Pseudo-deterministic Algorithms from a complexity point of view. |