Lower Bounds for Arithmetic Circuits via the Hankel Matrix We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the noncommutative settings. To analyse circuits we count their number of parse trees, which describe the nonassociative computations realised by the circuit. In the noncommutative setting a circuit computing a polynomial of degree d has at most 2O(d) parse trees. Previous superpolynomial lower bounds were known for circuits with up to 2d13e parse trees, for any eu003e0. Our main result is to reduce the gap by showing a superpolynomial lower bound for circuits with just a small defect in the exponent for the total number of parse trees, that is 2d1e, for any eu003e0. In the commutative setting a circuit computing a polynomial of degree d has at most 2O(d log d) parse trees.  We show a superpolynomial lower bound for circuits with up to 2d13e parse trees, for any eu003e0. When d is polylogarithmic in n, we push this further to up to 2d1e parse trees. While these two main results hold in the associative setting, our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish the polynomials (xy)z and x(yz). Our first and main conceptual result is a characterization result: we show that the size of the smallest circuit computing a given nonassociative polynomial is exactly the rank of a matrix constructed from the polynomial and called the Hankel matrix. This result applies to the class of all circuits in both commutative and noncommutative settings, and can be seen as an extension of the seminal result of Nisan giving a similar characterization for noncommutative algebraic branching programs. Our key technical contribution is to provide generic lower bound theorems based on analyzing and decomposing the Hankel matrix, from which we derive the results mentioned above. The study of the Hankel matrix also provides a unifying approach for proving lower bounds for polynomials in the (classical) associative setting.  We demonstrate this by giving alternative proofs of recent lower bounds as corollaries of our generic lower bound results.

On Computing Multilinear Polynomials Using Multir ic Depth Four Circuits In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of r (referred to as multiric circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better and better bounds as the value of r increases. Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree r computing a multilinear polynomial on nO(1) variables and degree d  o(n), must have size at least (nr1.1)sqrtdr when r is o(d) and is strictly less than n11.1. This bound however deteriorates with increasing r. It is a natural question to ask if we can prove a bound that does not deteriorate with increasing r or a bound that holds for a larger regime of r. We here prove a lower bound which does not deteriorate with r , however for a specific instance of d  d (n) but for a wider range of r. Formally, we show that there exists an explicit polynomial on nO(1) variables and degree xcex98(log2(n)) such that any depth four circuit of bounded individual degree r u003c n0.2 must have size at least exp(xcexa9 (log2 n)). This improvement is obtained by suitably adapting the complexity measure of Kayal et al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et al. (SIAM J. Computing, 2017).