Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices

We introduce the polynomial coefficient matrix and identify the maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove superpolynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results: —As our first main result, we prove that any homogeneous depth-3 circuit for computing the product of d matrices of dimension n × n requires (nd−1/2d) size. This improves the lower bounds in Nisan and Wigderson [1995] for d = ω(1). —As our second main result, we show that there is an explicit polynomial on n variables and degree at most2n for which any depth-3 circuit of product dimension at most10n (dimension of the space of affine forms feeding into each product gate) requires size 2(n). This generalizes the lower bounds against diagonal circuits proved in Saxena [2008]. Diagonal circuits are of product dimension 1. —We prove a n(log n) lower bound on the size of product-sparse formulas. By definition, any multilinear formula is a product-sparse formula. Thus, this result extends the known super-polynomial lower bounds on the size of multilinear formulas [Raz 2006]. —We prove a 2(n) lower bound on the size of partitioned arithmetic branching programs. This result extends the known exponential lower bound on the size of ordered arithmetic branching programs [Jansen 2008].