| Computer Science/Discrete Mathematics Seminar II | |
| Topic: | Derandomizing BPL? |
| Speaker: | Avi Wigderson |
| Affiliation: | School of Mathematics, IAS |
| Date: | Tuesday, February 26 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
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.