Computer Science/Discrete Mathematics Seminar II

This is the first talk in a three-part series presented together with Lijie Chen.

The series is intended to survey the fast-paced recent developments in the study of derandomization. We will present:

1. A revised version of the classical hardness vs randomness framework, converting new types of uniform lower bounds into non-black-box derandomization algorithms.
2. Unconditional derandomization of an important class of Merlin-Arthur protocols, and stronger circuit lower bounds from derandomization.
3. Optimal derandomization algorithms that incur essentially no runtime overhead (a.k.a "free lunch derandomization").

The first talk will provide background, setting the stage for the two subsequent ones that will focus on recent results. The talk will start with an overview of known results and of the main open problems in the area. Then we will prove several classical results that rely on the *reconstruction paradigm*, which we will define and analyze in the talk. Hopefully, we will also touch on the challenge in constructing derandomization algorithms that incur minimal time overhead.