The Taub Faculty of Computer Science Events and Talks

In the classical derandomization problem, we are given a description of a Boolean circuit, and want to deterministically approximate its acceptance probability, up to a small constant error (say, 1/6). This problem is intimately related to circuit lower bounds, and extensive efforts have been devoted in the last four decades to solving it, even for very weak circuit classes.

This survey talk is focused on a relaxed version of the problem, which was introduced a few years ago by Goldreich and Wigderson (2014). In the relaxed problem, called quantified derandomization, we only want to distinguish between circuits that accept *almost all* of their inputs and circuits that reject *almost all* of their inputs. This is formally an easier task -- so can we now solve it?

I'll survey surprisingly-tight results from recent papers by Goldreich, Wigderson, Viola, Cheng, Li, Kabanets, Lu, Chen, Doron, Ta-Shma, and myself.