An overview of quantified derandomization

Roei Tell

I will present an overview of quantified derandomization, including known results, barriers, and main open problems. 
In the classical derandomization problem, we are given as input a Boolean circuit, and want to deterministically decide 
whether it has high acceptance probability (say, 2/3 or more) or low acceptance probability (say, 1/3 or less). 
Quantified derandomization, introduced by Goldreich and Wigderson (2014), is the relaxed problem of deciding whether the 
acceptance probably of the circuit is extremely high (1-o(1)) or extremely low (o(1)). 

We currently have algorithms for quantified derandomization in a variety of settings and models (AC0, AC0[2], TC0, PIT...), as well 
as threshold results indicating that better algorithms will yield new circuit lower bounds, and impossibility results for 
some black box techniques. In some settings, the parameters of the known algorithms are remarkably close to parameters that 
will yield new circuit lower bounds.