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 space-bounded 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:00-11:00. Location: TBD.