{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibwyhnvuocqlnemsm7wxeptsk5qbn7zhq7azasfr62oy7iuz5ea3y",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mk6oyb4noc22"
  },
  "path": "/report/2026/061",
  "publishedAt": "2026-04-23T15:57:28.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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).",
  "title": "TR26-061 |  Polynomial Lower Bounds for Arithmetic Circuits over  Non-Commutative Rings | \n\n\tRan Raz"
}