Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: How to Detect Extreme Bias: An Overview of Quantified Derandomization
event speaker icon
Roei Tell (Weizmann Institute of Science)
event date icon
Wednesday, 22.05.2019, 12:30
event location icon
Taub 201
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.