Derandomizing Space-Bounded Computation

In this presentation from this fall’s joint boot camp for the programs on Spectral Theory Beyond Graphs and on Pseudorandomness & High-Dimensional Expansion, William Hoza presents an introduction to the “L vs. BPL” problem, which asks whether randomness is ever necessary for space-efficient computation. We present Part 1 here. See also Part 2.