Open AccessLower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version)
Author(s) -
Noam Nisan,
Avi Wigderson
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i43.19944
Subject(s) - arithmetic circuit complexity , mathematics , iterated function , arithmetic , monotone polygon , measure (data warehouse) , discrete mathematics , upper and lower bounds , arbitrary precision arithmetic , computer science , mathematical analysis , geometry , database
In this paper 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.