"Tighter Connections between Derandomization and Circuit Lower Bounds"
Marco Carmosino
(UCSD)
Monday, December 1st, 2014, 2:00 pm
EBU3B, Room 4258
Abstract:
It is known that many derandomization assumptions, either for particular algorithms or general complexity classes, imply circuit lower bounds. It is also known that circuit lower bound assumptions can be used to construct pseudorandom generators and thus derandomize algorithms. In some settings, circuit lower bounds and derandomization are equivalent. In the settings we study, the relationship less well-characterized.
We further develop the connections between circuit lower bounds and derandomization for each of the following three types of
derandomization:
* general derandomization of promiseBPP (connected to Boolean circuits),
* derandomization of Polynomial Identity Testing (PIT) over fixed finite fields (connected to arithmetic circuit lower bounds
over the same field), and
* derandomization of PIT over the integers (connected to arithmetic circuit lower bounds over the integers).
We show how to make these connections equivalences, although at the expense of showing the results for somewhat less common versions of complexity classes and for a less studied notion of inclusion.
joint work with Russell Impagliazzo; Valentine Kabanets; Antonina Kolokolova