### Rothschild Lecture: Pseudo Deterministic Algorithms and Applications to Cryptography

Goldwasser, S *(MIT)*

Thursday 12 April 2012, 17:00-18:00

Seminar Room 1, Newton Institute

#### Abstract

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.
We will exhibit a necessary and sufficient condition for the existence of a
pseudo-deterministic algorithm for an NP relation R.
Several examples of such 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
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 and pseudo deterministic sub-linear
algorithms for tasks which are impossible
to solve without randomization. We will discuss several such domains.