ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-105 | 29th June 2010 16:43

A note on circuit lower bounds from derandomization

RSS-Feed

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.



ISSN 1433-8092 | Imprint