Derandomization

To what extent is randomness essential for efficient algorithms? This workshop will investigate recent advances in the pursuit of converting randomized algorithms into deterministic ones, or ones that use few random bits. We will consider two main strands: unconditional results, and conditional results based on complexity-theoretic hardness assumptions. 

On the conditional front, our main goal will be derandomizing time-bounded computation. We will discuss new approaches and directions to this well-studied problem, such as super-fast derandomization, derandomization under weak and uniform assumptions, and non black-box methods. Recent work on space-bounded derandomization from hardness assumptions will be addressed as well, where the goal is to get hopefully provable hardness assumptions.

We will also be interested in the strong interplay between derandomization and adjacent areas in TCS such as catalytic computation, algebraic complexity, circuit complexity, and coding theory.

On the unconditional front, we will mainly consider space-bounded computation. We will investigate new techniques for constructing pseudorandom generators, weighted pseudorandom generators, and more.