Speaker:Peter Dixon

Pseudodeterminism-Completeness

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: 

Meeting link:

https://iastate.webex.com/iastate/j.php?MTID=ma0e164f091f34a4cae5d5ef4d2c3d03b 

Meeting number:

120 997 9831

Password:

gradwebinar

Host key:

232846