Lower Bounds on Arithmetic Circuits via Partial Derivatives (Preliminary Version)

Noam Nisan
Avi Wigderson

August 1995

Abstract:

In this paper we describe a new technique for obtaining lower bounds on restriced classes of nonmonotone 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

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.