Abstract
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 the circuit 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)). It is a potentially easier problem, which (in some settings) does not necessarily imply new circuit lower bounds. Interestingly, for many circuit classes, the parameters for which we can construct quantified derandomization algorithms are remarkably close to parameters that will yield new standard derandomization algorithms (and new lower bounds). Two prominent classes for which this is the case are AC0 and TC0. In the talk I will survey some of the known results for these classes, as well as for other classes and for diferent settings in which quantified derandomization is relevant (these results are from works by Goldreich, Wigderson, Viola, Chen, Li, Kabanets, Lu, and myself). In addition we will see techniques that were used to prove these results, limitations of these techniques in a black box setting, and main open problems.