Non-commutative circuits and the sum-of-squares problem

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degree four polynomials, the classical sum-of-squares problem: find the smallest n such that there exists an identity (x₁²+x₂²+•• + x_k²)• (y₁^2+y₂²+•• + y_k²)= f₁²+f₂²+ ... +f_n², where each f_i = f_i(X,Y) is bilinear in X={x₁,...,x_k} and Y={y₁,..., y_k}. Over the complex numbers, we show that a sufficiently strong super-linear lower bound on n in, namely, n ≥ k^1+ε with ε >0, implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent.

More generally, we consider such sum-of-squares identities for any M polynomial h(X,Y), namely: h(X,Y) = f₁²+f₂²+...+f_n².

Again, proving n ≥ k^1+ε in for any explicit h over the complex numbers gives an exponential lower bound for the non-commutative permanent. Our proofs relies on several new structure theorems for non-commutative circuits, as well as a non-commutative analog of Valiant's completeness of the permanent.

We proceed to prove such super-linear bounds in some restricted cases. We prove that n ≥ Ω(k^6/5) in (1), if f₁,..., f_n are required to have integer coefficients. Over the real numbers, we construct an explicit M polynomial h such that n in (2) must be at least Ω(k²). Unfortunately, these results do not imply circuit lower bounds. We also present other structural results about non-commutative arithmetic circuits. We show that any non-commutative circuit computing an ordered non-commutative polynomial can be efficiently transformed to a syntactically multilinear circuit computing that polynomial. The permanent, for example, is ordered. Hence, lower bounds on the size of syntactically multilinear circuits computing the permanent imply unrestricted non-commutative lower bounds. We also prove an exponential lower bound on the size of non-commutative syntactically multilinear circuit computing an explicit polynomial. This polynomial is, however, not ordered and an unrestricted circuit lower bound does not follow.