Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings

Abstract

We prove a lower bound of $\Omega \left(n^{1.5}\right)$ for the number of product gates in non-commutative arithmetic circuits for an explicit $n$-variate degree-$n$ polynomial $f_n$ (over every field). We observe that this implies that over certain non-commutative rings $R$, any arithmetic circuit that computes the induced polynomial function $f_n:R^n\to R$, using the ring operations of addition and multiplication in $R$, requires at least $\Omega \left(n^{1.5}\right)$ multiplications. More generally, for any $d\ge 2$ and sufficiently large $n$, we obtain a lower bound of $\Omega \left(d\sqrt{n}\right)$ for $n$-variate degree-$d$ polynomials, for both these models. Prior to our work, the only known lower bounds for the size of non-commutative circuits, or for the size of arithmetic circuits over any ring, were slightly super-linear in $\max \{n,d\}$: $\Omega \left(n\log d\right)$ by Baur and Strassen, and $\Omega \left(d\log n\right)$ by Nisan. (Nisan's bound was proved for non-commutative arithmetic circuits and implies a bound for arithmetic circuits over non-commutative rings by our observation).