University of Cambridge > > Isaac Newton Institute Seminar Series > Rothschild Lecture: Pseudo Deterministic Algorithms and Applications to Cryptography

Rothschild Lecture: Pseudo Deterministic Algorithms and Applications to Cryptography

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2021, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity