Videos

Derandomizing BPL?

Presenter
February 26, 2013
Keywords:
  • Avi Wigderson
  • Computer Science and Discrete Mathematics (CSDM)
Abstract
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.