Einstein Lectures

Einstein Lectures 2019
Einstein Lectures 2019

Pseudo Deterministic Algorithms and Proofs

Dienstag, 08.10.2019, 17:15 Uhr

Professor Shafi Goldwasser
Professor Shafi Goldwasser
Bild: ©

In this talk Shafi Goldwasser will describe what is known about pseudo-deterministic algorithms in the sequential, sub-linear and parallel setting. She will also describe an extension of pseudo-deterministic algorithms to interactive proofs for search problems where the verifier is guaranteed with high probability to deliver the same output on different executions, regardless of the prover strategies.

Veranstaltende: Universität Bern und Albert Einstein Gesellschaft
Redner, Rednerin: Professor Shafi Goldwasser
Datum: 08.10.2019
Uhrzeit: 17:15 - 18:45 Uhr
Ort: Aula
Hauptgebäude
Hochschulstrasse 4
3012 Bern
Merkmale: Öffentlich
kostenlos

Abstract

Probabilistic algorithms for both decision and search problems can offer significant complexity improvements over deterministic algorithms. One major difference, however, is that they may output different solutions for different choices of randomness. This is less than desirable in settings where uniqueness of output is important such as in the generation of system-wide cryptographic parameters or in a distributed setting where different sources of randomness are used. Pseudo-deterministic algorithms are a class of randomized search algorithms, which output a unique answer with high probability. Intuitively, they are indistinguishable from deterministic algorithms by a polynomial time observer of their input/output behavior. In this talk I will describe what is known about pseudo-deterministic algorithms in the sequential, sub-linear and parallel setting. I will also describe an extension of pseudo-deterministic algorithms to interactive proofs for search problems where the verifier is guaranteed with high probability to deliver the same output on different executions, regardless of the prover strategies.