Computer Science/Discrete Mathematics Seminar II

This is the second talk in a three-part series presented together with Roei Tell.

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 second talk will present the recent developments on proving circuit lower bounds from non-trivial derandomization (a.k.a., the algorithmic method).  As the main focus, I will show how to derandomize Merlin-Arthur protocols with ACC^0 verifiers in nondeterministic quasi-polynomial time infinitely often and consequently deduce ACC^0 lower bounds.

I will first present a recent perspective on the algorithmic method that decomposes the whole proof into three conceptual ingredients and show how these three ingredients lead to new circuit lower bounds.  Next, I will explain one of the ingredients in more detail: an approach for unconditionally derandomizing Merlin-Arthur protocols whose verifiers have small circuits from a certain circuit class.