Pseudo deterministic algorithms and proofs

In this talk I will describe what is known about pseudo-deterministic algorithms in the sequential, sub-linear and parallel setting. 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.

You can listen to Pseudo deterministic algorithms and proofs online on Radio and Podcast. Open the player on this page to stream the available audio.

Pseudo deterministic algorithms and proofs is an episode from Federated Logic Conference (FLoC) 2018 by Oxford University.

This episode is 66:47 long.

This episode was published on Jul 13, 2018.

Yes. Use the heart button on the episode page to add it to your favorite episodes list.

Yes. This page shows related episodes from Federated Logic Conference (FLoC) 2018 when more episodes are available from the podcast feed.