Lower Bounds on Arithmetic Circuits via Partial Derivatives

Submitted by smcneil on Mon, 2012-01-16 00:00
Author: 
N. Nisan
A. Wigderson
Publication: 
Preliminary version in Proceedings of the 36th Foundations of Computer Science ( FOCS), pp. 16-25, 1995.
Computational Complexity, vol. 6, no. 3, pp. 217-234, 1996.
Year: 
1996
Abstract: 
http://www.math.ias.edu/~avi/PUBLICATIONS/ABSTRACT/nw96.pdf
Files
File: 
Journal version (pdf)
Journal version (ps)