Lower Bounds for Arithmetic Circuits via the Hankel Matrix

We study the complexity of representing polynomials by arithmeticcircuits in both the commutative and the non-commutative settings.Our approach goes through a precise understanding of the morerestricted setting where multiplication is not associative, meaningthat we distinguish (xy)z from x(yz). Our first and main conceptual result is a characterization result:We show that the size of the smallest circuit computing a givennon-associative polynomial is exactly the rank of a matrixconstructed from the polynomial and called the Hankel matrix. Thisresult applies to the class of all circuits in both commutative andnon-commutative settings, and can be seen as an extension of theseminal result of Nisan giving a similar characterization fornon-commutative algebraic branching programs. The study of the Hankel matrix provides a unifying approach forproving lower bounds for polynomials in the (classical) associativesetting. Our key technical contribution is to provide generic lowerbound theorems based on analyzing and decomposing the Hankel matrix.We obtain significant improvements on lower bounds for circuits withmany parse trees, in both (associative) commutative andnon-commutative settings, as well as alternative proofs of recentresults proving superpolynomial and exponential lower bounds fordifferent classes of circuits as corollaries of our characterizationand decomposition results.