Randomized algorithms are useful for many problems, like generating large prime numbers or learning distributions. However, these algorithms may output different solutions each time they're run. In some contexts, like distributed computing, this may be undesirable. Pseudodeterministic algorithms are algorithms that still use randomness, but consistently output a particular solution. While pseudodeterministic algorithms for many problems are known, some problems are quite hard to solve pseudodeterministically. So we do what any complexity theorist does when they can't solve something: we develop a notion of completeness for pseudodeterministic problems, and show some natural problems are pseudodeterminism-complete.
Bio: Peter Dixon is a PhD student at Iowa State University, working with Dr. Pavan Aduri on complexity theory and randomized algorithms.
Join on WebEx:
120 997 9831