We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results : 1. 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 Q(n~(d-1)/2~d) size. This improves the lower bounds in for d = ω(1). 2. As our second main result, we show that there is an explicit polynomial on n variables and degree at most n/2- for which any depth-3 circuit C of product dimension at most n/(10) (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. Diagonal circuits are of product dimension 1. 3. 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. 4. 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.
展开▼
