Workshop Details

Lifting theorems translate lower bounds for simple models of computation (e.g., decision trees) to lower bounds for more powerful models (e.g., communication protocols). These techniques have recently enabled progress on core questions in communication complexity, circuit complexity, proof complexity, and LP/SDP extension complexity. This tutorial is an introduction to these topics, with a special emphasis on open problems.

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.