Derandomizing BPL?
Series:
Computer Science/Discrete Mathematics
Avi Wigderson
School of Mathematics, IAS
Date & Time:
Tue, 02/26/2013 - 10:30 - 12:30
Location:
S-101
Video Link:
I will survey some of the basic approaches to derandomizing Probabilistic Logspace computations, including the "classical" Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the Saks-Zhou algorithm and some more recent approaches. We'll see why each falls short of complete derandomization, BPL=L, hopefully motivating further work on this basic problem.
45402
Dorothea Phares
phares@ias.edu
Wed, 12/19/2012 - 18:21
Thu, 02/21/2013 - 15:11