Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-061 | 23rd April 2026 18:55

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings

RSS-Feed




TR26-061
Authors: Ran Raz
Publication: 23rd April 2026 18:57
Downloads: 241
Keywords: 


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 \rightarrow 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\geq 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).



ISSN 1433-8092 | Imprint