Probabilistic computations: Mild derandomizatons and zero-knowledge classes

Abstract

Random algorithms have a unique place in complexity theory as a model of computation that ispotentially more powerful than “normal” algorithms, and is also practical. However, it is still notclear how much more power randomness adds. The primary goal in studying random algorithmsis derandomization – some method to simulate random algorithms without actually using random-ness. 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 resultswould have major implications. Finally, we show new containments and oracle separations betweentraditional random classes and zero-knowledge proofs.