Shafi Goldwasser
Massachusetts Institute of Technology
Time: Friday, April 12th, 2013, 2:30 pm
Location: CEWIT 200

Pseudo Deterministic Algorithms: Possibilities and Limits

We describe a new type of probabilistic search algorithm: a randomized algorithm which is guaranteed to run in expected polynomial time, and with high probability produce correct and unique solution. These algorithms are pseudo-deterministic: they can not be distinguished from deterministic algorithms in polynomial time by a probabilistic polynomial time observer with black box access.

The notion of pseudo-deterministic algorithms (or more generally computations) is interesting beyond just sequential polynomial time algorithms, in other domains where the use of randomization is essential such as sublinear time algorithms and fault tolerance distributed algorithms. In this talk we will discuss the possibilities and limits of pseudo deterministic algorithms.