DocumentCode
3388700
Title
Lower bounds on arithmetic circuits via partial derivatives
Author
Nisan, Noam ; Wigderson, Avi
Author_Institution
Inst. of Comput. Sci., Hebrew Univ., Jerusalem, Israel
fYear
1995
fDate
23-25 Oct 1995
Firstpage
16
Lastpage
25
Abstract
We describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials and iterated matrix products
Keywords
computational complexity; digital arithmetic; logic circuits; minimisation of switching nets; polynomials; arithmetic circuits; complexity measure; lower bounds; multivariate polynomials; partial derivatives; restricted classes; Analog computers; Circuit simulation; Computer science; Digital arithmetic; Heart; Polynomials; Symmetric matrices; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location
Milwaukee, WI
ISSN
0272-5428
Print_ISBN
0-8186-7183-1
Type
conf
DOI
10.1109/SFCS.1995.492458
Filename
492458
Link To Document