Skip to main content
Home

Main navigation

  • Home
  • Series
  • People
  • Depts & Colleges
  • Open Education

Main navigation

  • Home
  • Series
  • People
  • Depts & Colleges
  • Open Education

Pseudo deterministic algorithms and proofs

Series
Federated Logic Conference (FLoC) 2018
Video Embed
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.

More in this series

View Series
Journey of a Molecular Detective; David Sherratt

Continuous Reasoning: Scaling the impact of formal methods

Formal reasoning about programs is one of the oldest and most fundamental research directions in computer science. It has also been one of the most elusive.
Previous
Journey of a Molecular Detective; David Sherratt

Looking Backward; Looking Forward

An invited talk by the Emeritus Hillman University Professor of Computer Science, Philosophy and Mathematical Logic at Carnegie Mellon University at FLoC2018
Next

Episode Information

Series
Federated Logic Conference (FLoC) 2018
People
Shafi Goldwasser
Keywords
algorithms
randomness
floc
computer science
Department: Department of Computer Science
Date Added: 13/07/2018
Duration: 01:06:47

Subscribe

Apple Podcast Video Video RSS Feed

Download

Download Video

Footer

  • About
  • Accessibility
  • Contribute
  • Copyright
  • Contact
  • Privacy
'Oxford Podcasts' Twitter Account @oxfordpodcasts | MediaPub Publishing Portal for Oxford Podcast Contributors | Upcoming Talks in Oxford | © 2011-2022 The University of Oxford