## Tighter Connections between Derandomization and Circuit Lower Bounds

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

### Abstract

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

- general derandomization of promise-BPP (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 *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:

- We give the first proof that a non-trivial, nondeterministic
subexponential-time, algorithm for PIT over a
*fixed finite field*yields arithmetic circuit lower bounds. - We get a similar result for the case of PIT over the integers, strengthening a result of Jansen and Santhanam, 2012 (by removing the need for advice).
- We derive a Boolean circuit lower bound for NEXP$\cap$coNEXP from the assumption of sufficiently strong non-deterministic derandomization of promise-BPP (without advice), as well as from the assumed existence of an NP-computable non-empty property of Boolean functions useful for proving superpolynomial circuit lower bounds in the sense of natural proofs of Razborov and Rudich (1987); this strengthens the related results of Impagliazzo et al. (2002).
- Finally, we turn all of these implications into equivalences for appropriately defined promise classes and for a notion of robust inclusion/separation (inspired by Fortnow and Santhanam (2011)) that lies between the classical ``almost everywhere'' and ``infinitely often'' notions.

### Versions

- conference version in
*Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), August 24-26, 2015*, pages 645-658, 2015.