New Lower Bounds against Homogeneous Non-Commutative Circuits

Abstract

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega (d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega (nd)$, if $d\le n$, or $\Omega (nd\frac{\log n}{\log d})$, if $d\ge n$. Under the same assumptions, we also give a quadratic lower bound for the ordered version of the central symmetric polynomial.