Tighter Connections between Derandomization and Circuit Lower Bounds

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova


We tighten the connections between circuit lower bounds and derandomization for each of the following three types of derandomization:

We show how to make these connections uniform equivalences, although at the expense of using somewhat less common versions of complexity classes and for a less studied notion of inclusion.

Our main results are as follows: