Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908990078713856 |
|---|---|
| author | Raz, Ran |
| author_facet | Raz, Ran |
| contents | We prove a lower bound of $Ω\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 $Ω\left(n^{1.5}\right)$ multiplications.
More generally, for any $d\geq 2$ and sufficiently large $n$, we obtain a lower bound of $Ω\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\}$: $Ω\left(n\log d\right)$ by Baur and Strassen, and $Ω\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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_22006 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings Raz, Ran Computational Complexity We prove a lower bound of $Ω\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 $Ω\left(n^{1.5}\right)$ multiplications. More generally, for any $d\geq 2$ and sufficiently large $n$, we obtain a lower bound of $Ω\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\}$: $Ω\left(n\log d\right)$ by Baur and Strassen, and $Ω\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). |
| title | Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.22006 |