Non-commutative circuits and the sum-of-squares problem
Pavel Hrubeš, Avi Wigderson, Amir Yehudayoff · 2010
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 (x12+x22+•• + xk2)• (y1^2+y22+•• + yk2)= f12+f22+ ... +fn2, where each fi = fi(X,Y) is bilinear in X={x1,... ,xk} and Y={y1,..., yk}. Over the complex numbers, we show that a sufficiently strong super-linear lower bound on n in, namely, n ≥ k1+ε with ε >0, implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent.