Pseudo deterministic algorithms and proofs

This lecture was recorded: available in our gallery.

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 makes correctness amplification impossible for search algorithms and is less than desirable in setting where uniqueness of output is important such as generation of system wide cryptographic parameters or 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. We will also describe an extension of pseudo-deterministic algorithms to interactive proofs for search problems where the verifier is guaranteed with high probability to output the same output on different executions, regardless of the prover strategies. Based on joint work with Goldreich, Ron, Grossman and Holden.

Bio

Shafi Goldwasser is the Director of the Simons Institute for the Theory of Computing at UC Berkeley. She is also the RSA Professor of Electrical Engineering and Computer Science at MIT, and a professor of computer science and applied mathematics at the Weizmann Institute of Science in Israel. Goldwasser received a BS in applied mathematics from Carnegie Mellon University in 1979, and MS and PhD in computer science from the UC Berkeley in 1984.

Goldwasser was the recipient of ACM Turing Award for 2012. She is also the recipient of the Gödel Prize in 1993 and 2001 for her work on interactive proofs and connections to approximation, and was awarded the ACM Grace Murray Hopper award in 1996, the RSA award in mathematics in 1998, the ACM Athena award for women in computer science in 2008, the Benjamin Franklin Medal in Computer and Cognitive Science in 2010, the IEEE Emanuel R. Piore award in 2011, the Barnard College Medal of Distinction 2016, and the Suffrage Science Award from Imperial College 2016. She is a member of the AAAS, NAS, NAE, the Israeli Academy of Science, the London Mathematical Society, and the Russian Academy of Science.