COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## Rothschild Lecture: Pseudo Deterministic Algorithms and Applications to CryptographyAdd to your list(s) Download to your calendar using vCal - Goldwasser, S (MIT)
- Thursday 12 April 2012, 17:00-18:00
- Seminar Room 1, Newton Institute.
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. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other lists80000 Hours Cambridge Russian Society Multidisciplinary Gender Research Seminars## Other talksClimate Change: Protecting Carbon Sinks Ethics for the working mathematician, seminar 11: Winning with mathematics On the elastic-brittle versus ductile fracture of lattice materials Dispersion for the wave and the Schrodinger equations outside strictly convex obstacles Building intuition about coherence |