LOWER BOUNDS ON ARITHMETIC CIRCUITS VIA PARTIAL DERIVATIVES

In this paper we describe a new technique for obtaining lower bounds o n 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 tech nique to obtain new lower bounds for computing symmetric polynomials ( that hold over fields of characteristic zero) and iterated matrix prod ucts (that hold for all fields).