Computer Science/Discrete Mathematics Seminar I

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past several years, there has been some exciting progress toward proving this conjecture. Thanks to recent work, we have new pseudorandom generators (PRGs), new black-box derandomization algorithms (generalizations of PRGs), and new non-black-box derandomization algorithms. In this talk, we will survey these recent developments, with an emphasis on Laplacian methods, error reduction procedures, and weighted pseudorandom generators.