Ph.D. Final Oral Exam: Peter Dixon

Peter Dixon
Wednesday, May 12, 2021 - 10:00am
Event Type: 

Probabilistic Computations: Mild Derandiimzatons and Zero Knowledge Classes

Random algorithms have a unique place in complexity theory as a model of computation that is potentially more powerful than "normal" algorithms, and is also practical. However, it is still not clear how much more power randomness adds. The primary goal in studying random algorithms is derandomization -- some method to simulate random algorithms without actually using randomness. While full derandomization is quite difficult, we show some weak derandomization results -- one using advice, and one using multi-pseudodeterminism. We show that improving these results would have major implications. Finally, we show new containments and oracle separations between traditional random classes and zero-knowledge proofs.

Committee: Pavan Aduri (major professor), Soma Chaudhuri, David Fernandez-Baca, Jack Lutz, and Bernard Lidicky

Join on WebEx:  Meeting number: 120 188 6016 Password: zCvAM3VqG26