Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings

Ran Raz

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$ (…