Omer Reingold, Stanford University

Abstract

One of the most important complexity-theoretic challenges is showing that randomized algorithms are not much more powerful than deterministic algorithms. Specifically, the two main challenges are to show that randomness "cannot save time" and that randomness ``cannot save memory". Our focus here is on the latter.  More precisely, the ultimate goal is to show that every problem solvable by a randomized space-bounded algorithm is also solvable by a deterministic algorithm that only uses a constant factor more space (where space refers to memory).  By standard padding arguments, this is equivalent to showing that randomized logspace equals deterministic logspace (i.e. RL = L or BPL = L, depending on whether we consider 1-sided or 2-sided error). This problem has drawn a considerable attention in recent decades, leading to beautiful research. In this talk, we will discuss several separate threads of research which produced exciting and fundamental progress in this area from the last few years. Specific topics will include deterministic approximations of random walks in small space, generators that fool constant-width read-once branching programs, and pseudorandom pseudo-distributions that fool read-once branching programs and have almost optimal dependence on the error parameter. With the fast pace developments in this area, we will leave room for any last-minute breakthroughs.

View videos: Part 1     Part 2