Volume 7 (2011)
Article 12 pp. 177-184
[Note]
On Circuit Lower Bounds from Derandomization
Received: December 7, 2010
Published: September 12, 2011
Published: September 12, 2011
Keywords: circuit lower bounds, derandomization, Polynomial Identity Testing
Categories: note, complexity theory, circuit complexity, lower bounds, derandomization, polynomials - multivariate, 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.