Seminar on Space Bounded Computation & Randomness
Fall 2024/5
About the seminar
One of the central problems in complexity theory is the BPL vs. L problem, which asks whether randomness adds computational power to spacebounded algorithms. This problem has been studied for decades, with significant advances made in recent years.
In this seminar, we will cover (mostly) modern works on the problem, including the use of combinatorial and spectral methods. We will also discuss the related and fascinating notion of catalytic computation, where one attempts to compute with an already full memory—a highly counterintuitive and useful idea.
After a brief introduction by the lecturer (one or two lectures), you will be asked to select a paper from the list below (which will be more meaningful after the introduction) and present it to the class. Further details about the "bidding" process and expectation of your presentation will be provided at the start of the seminar.
When & where
Sunday 9:0011:00. Location: TBD.
List of Papers
The list of papers is roughly divided into three categories:
Combinatorial methods

Pseudorandom Generators for SpaceBounded Computation and the INW Generator

NearOptimal Derandomization of MediumWidth Branching Programs

Pseudorandom Generators for ReadOnce Branching Programs, in any Order (this work has a "Fourieranalytic flavor").
Spectral methods

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting
Catalytic computation