Speaker:Peter Dixon

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: https://iastate.webex.com/iastate/j.php?MTID=md2acaf39fa3601f7e4dc3d2665f78af5  Meeting number: 120 188 6016 Password: zCvAM3VqG26