Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

Bin Fu

We show that derandomizing polynomial identity testing over an arbitrary finite field implies that NEXP does not have polynomial size boolean circuits. In other words, for any fini…