pdf icon
Volume 7 (2011) Article 12 pp. 177-184 [Note]
On Circuit Lower Bounds from Derandomization
Received: December 7, 2010
Published: September 12, 2011
Download article from ToC site:
[PDF (188K)]    [PS (556K)]    [PS.GZ (188K)]
[Source ZIP]
Keywords: circuit lower bounds, derandomization, polynomial identity testing
ACM Classification: F.1.2, F.1.3
AMS Classification: 68Q10, 68Q15, 68Q17

Abstract: [Plain Text Version]

We present an alternate proof of the result by Kabanets and Impagliazzo (2004) 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.