Pseudo Deterministic Algorithms
Speaker: Shafi Goldwasser , CSAIL, MIT
Date: March 20 2012
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
We describe a new type of probabilistic search algorithm which we call
Bellagio Algorithms: 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.
We show a necessary and sufficient condition for the existence of a
Bellagio Algorithm for an NP relation R: R has a Bellagio algorithm if
and only if it is deterministically reducible to some decision problem
in BPP. Several examples of Bellagio algorithms, for problems in
number theory, algebra and graph theory which improve on deterministic
solutions, will also be discussed. We note that the characterization
scales up.
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. For example, one can define and obtain pseudo-deterministic
fault tolerance distributed algorithms for tasks which are impossible
to solve without randomization. We will discuss several such domains.
See other events that are part of Theory Colloquium 2011/2012
See other events happening in March 2012
