On Circuit Lower Bounds from Derandomization Download as PDF


Abstract

We present an alternate proof of the result by Kabanets and Impagliazzo that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.


dieter@cs.wisc.edu