pith. sign in

arxiv: 2604.22006 · v1 · submitted 2026-04-23 · 💻 cs.CC

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings

Ran Raz This is my paper

Pith reviewed 2026-05-08 12:48 UTC · model grok-4.3

classification 💻 cs.CC
keywords non-commutative arithmetic circuitslower boundspolynomial complexitycircuit sizearithmetic circuitsexplicit polynomials
0
0 comments X

The pith

Non-commutative arithmetic circuits for an explicit n-variate degree-n polynomial require Omega(n to the 1.5) product gates over any field.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a polynomial lower bound on the number of multiplications needed to compute certain explicit polynomials in the non-commutative setting. For an n-variate polynomial of total degree n, any non-commutative arithmetic circuit must use at least roughly n to the power 1.5 product gates. The same bound applies to the number of ring multiplications when the polynomial is evaluated over suitable non-commutative rings. A more general version gives Omega(d times square root of n) for degree-d polynomials when d is fixed and n is large. These results improve on the previous best bounds, which were only slightly super-linear in the input size.

Core claim

We prove a lower bound of Omega(n^{1.5}) for the number of product gates in non-commutative arithmetic circuits for an explicit n-variate degree-n polynomial f_n over every field. This implies that over certain non-commutative rings R, any arithmetic circuit computing the induced function f_n from R^n to R requires at least Omega(n^{1.5}) multiplications. For any fixed d at least 2 and large enough n, the bound becomes Omega(d sqrt(n)) for both the circuit model and the ring model.

What carries the argument

The explicit n-variate degree-n polynomial f_n together with direct analysis of product-gate count in non-commutative circuits.

If this is right

  • Any circuit over a non-commutative ring computing the corresponding function must use Omega(n^{1.5}) multiplications.
  • For fixed degree d at least 2, the product-gate lower bound scales as Omega(d sqrt(n)) for large n.
  • The new bound is polynomial rather than logarithmic and holds uniformly over every field.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result separates non-commutative circuit complexity from the commutative case for at least one explicit family.
  • Similar techniques might be tested on other natural polynomials to obtain tighter lower bounds.
  • The ring-model implication shows that algebraic hardness can be transferred from circuits to direct ring computations.

Load-bearing premise

The chosen explicit polynomial f_n truly requires many product gates under the standard non-commutative circuit rules.

What would settle it

Exhibit a non-commutative arithmetic circuit for the paper's specific f_n that uses fewer than n to the 1.5 product gates.

read the original 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).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves an Ω(n^{1.5}) lower bound on the number of product gates in non-commutative arithmetic circuits (over any field) for an explicit n-variate degree-n polynomial f_n. It shows that the same bound holds for arithmetic circuits computing the induced function f_n : R^n → R over non-commutative rings R, and generalizes to an Ω(d √n) lower bound for n-variate degree-d polynomials (d ≥ 2, n large) in both models. This improves on the prior slightly super-linear bounds Ω(n log d) (Baur-Strassen) and Ω(d log n) (Nisan).

Significance. If the central proof holds, the result is a notable advance: it supplies the first polynomial lower bounds for non-commutative arithmetic circuits and for arithmetic circuits over non-commutative rings, moving well beyond the previous slightly super-linear regime. The explicitness of f_n, the direct (non-reduction) proof technique, and the clean extension from the circuit model to the ring model are strengths that strengthen the contribution.

minor comments (2)
  1. [Introduction] The precise definition and construction of the explicit polynomial f_n should be stated in the introduction (or as a numbered definition in §2) rather than deferred to the proof section, to make the explicitness claim immediately verifiable by readers.
  2. [§4] In the generalization to degree-d polynomials, the dependence on d in the Ω(d √n) bound should be accompanied by a brief remark on the range of d for which the argument applies (e.g., whether d = o(√n) is required).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation to accept. The referee's summary correctly identifies the main results: the first polynomial lower bounds on the number of product gates in non-commutative arithmetic circuits (and the induced bounds for arithmetic circuits over non-commutative rings), together with the generalization to degree-d polynomials.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes its Ω(n^{1.5}) lower bound via a direct argument on an explicitly constructed n-variate degree-n polynomial f_n in the standard non-commutative circuit model. The extension to induced functions over non-commutative rings follows from a straightforward observation that does not rely on any fitted parameters or self-referential definitions. Prior bounds (Baur-Strassen, Nisan) are cited only as background; the new result and the general Ω(d √n) bound for degree-d polynomials are derived independently from the paper's own construction and proof. No load-bearing self-citation, ansatz smuggling, or renaming of known results occurs. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definition of non-commutative arithmetic circuits and the existence of an explicit hard polynomial; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math Arithmetic circuits compute polynomials via addition and multiplication gates over a field or ring.
    This is the conventional model used throughout algebraic complexity.
  • domain assumption Multiplication in the ring or circuit is non-commutative.
    The non-commutativity is the key setting that distinguishes the model from the commutative case.

pith-pipeline@v0.9.0 · 5529 in / 1250 out tokens · 87320 ms · 2026-05-08T12:48:10.309087+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Vikraman Arvind, Srikanth Srinivasan: On the Hardness of the Noncommutative Determinant. Comput. Complex. 27(1): 1-29 (2018)

    work page 2018

  2. [2]

    Markus Bläser: Noncommutativity Makes Determinants Hard. Inf. Comput. 243: 133-144 (2015)

    work page 2015

  3. [3]

    Shokrollahi: Algebraic Complexity Theory

    Peter Bürgisser, Michael Clausen, Mohammad A. Shokrollahi: Algebraic Complexity Theory. Vol. 315. Springer Science and Business Media, 2013

    work page 2013

  4. [4]

    FOCS 2019: 845-861

    Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson: Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes. FOCS 2019: 845-861

    work page 2019

  5. [5]

    Walter Baur, Volker Strassen: The Complexity of Partial Derivatives. Theor. Comput. Sci. 22: 317-330 (1983)

    work page 1983

  6. [6]

    CCC 2005: 92-99

    Andrej Bogdanov, Hoeteck Wee: More on Noncommutative Polynomial Identity Testing. CCC 2005: 92-99

    work page 2005

  7. [7]

    CCC 2023: 13:1-13:10

    Prerona Chatterjee, Pavel Hrubes: New Lower Bounds Against Homogeneous Non-Commutative Circuits. CCC 2023: 13:1-13:10

    work page 2023

  8. [8]

    STOC 2011: 499-508

    Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan: Almost Settling the Hardness of Noncommutative Determinant. STOC 2011: 499-508

    work page 2011

  9. [9]

    Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin: Hardness Amplification for Non-Commutative Arithmetic Circuits

    Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin: Hardness Amplification for Non-Commutative Arithmetic Circuits. CCC 2018: 12:1-12:16

    work page 2018

  10. [10]

    Steve Chien, Alistair Sinclair: Algebras with Polynomial Identities and Computing the Determinant. SIAM J. Comput. 37(1): 252-266 (2007)

    work page 2007

  11. [11]

    Forbes, Amir Shpilka: Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs

    Michael A. Forbes, Amir Shpilka: Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. FOCS 2013: 243-252

    work page 2013

  12. [12]

    CCC 2014: 181-187

    Craig Gentry: Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington's Theorem. CCC 2014: 181-187

    work page 2014

  13. [13]

    FOCS 2016: 109-117

    Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson: A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. FOCS 2016: 109-117

    work page 2016

  14. [14]

    FOCS 1977: 171-174

    Laurent Hyafil: The Power of Commutativity. FOCS 1977: 171-174

    work page 1977

  15. [15]

    John Hopcroft, Leslie Kerr: On Minimizing the Number of Multiplications Necessary for Matrix Multiplication. SIAM J. Appl. Math. 20(1): 30-36, 1971

    work page 1971

  16. [16]

    Theory Comput

    Pavel Hrubeš, Avi Wigderson: Non-Commutative Arithmetic Circuits with Division. Theory Comput. 11: 357-393 (2015)

    work page 2015

  17. [17]

    CCC 2010: 280-290

    Pavel Hrubeš, Avi Wigderson, Amir Yehudayoff: Relationless Completeness and Separations. CCC 2010: 280-290

    work page 2010

  18. [18]

    Pavel Hrubeš, Avi Wigderson, Amir Yehudayoff: Non-Commutative Circuits and the Sum-of-Squares Problem. J. Amer. Math. Soc. 24 (2011), 871-898

    work page 2011

  19. [19]

    Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan: Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees. Comput. Complex. 28(3): 471-542 (2019)

    work page 2019

  20. [20]

    Guillaume Lagarde, Guillaume Malod, Sylvain Perifel: Non-Commutative Computations: Lower Bounds and Polynomial Identity Testing. Chic. J. Theor. Comput. Sci. 2019 (2019)

    work page 2019

  21. [21]

    Theory Comput

    Nutan Limaye, Guillaume Malod, Srikanth Srinivasan: Lower Bounds for Non-Commutative Skew Circuits. Theory Comput. 12(1): 1-38 (2016)

    work page 2016

  22. [22]

    STOC 2022: 416-425

    Nutan Limaye, Sébastien Tavenas, Srikanth Srinivasan: Set-Multilinear and Non-Commutative Formula Lower Bounds for Iterated Matrix Multiplication. STOC 2022: 416-425

    work page 2022

  23. [23]

    Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. J. ACM 72(4): 26:1-26:35 (2025)

    work page 2025

  24. [24]

    STOC 1991: 410-418

    Noam Nisan: Lower Bounds for Non-Commutative Computation (Extended Abstract). STOC 1991: 410-418

    work page 1991

  25. [25]

    Noam Nisan, Avi Wigderson: Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Comput. Complex. 6(3): 217-234 (1997)

    work page 1997

  26. [26]

    Theory Comput

    Ran Raz: Separation of Multilinear Circuit and Formula Size. Theory Comput. 2(6): 121-135 (2006)

    work page 2006

  27. [27]

    Ran Raz: Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size. J. ACM 56(2): 8:1-8:17 (2009)

    work page 2009

  28. [28]

    Ran Raz, Amir Shpilka: Deterministic Polynomial Identity Testing in Non-Commutative Models. Comput. Complex. 14(1): 1-19 (2005)

    work page 2005

  29. [29]

    URL: https://github.com/dasarpmar/lowerbounds-survey

    Ramprasad Saptharishi: A Survey of Lower Bounds in Arithmetic Circuit Complexity. URL: https://github.com/dasarpmar/lowerbounds-survey

    work page

  30. [30]

    ITCS 2026: 115:1–115:9

    Pratik Shastri: Lower Bounds for Noncommutative Circuits with Low Syntactic Degree. ITCS 2026: 115:1–115:9

    work page 2026

  31. [31]

    Numerische Mathematik, 20(3): 238–251, 1973

    Volker Strassen: Die Berechnungskomplexitat Von Elementarsymmetrischen Funktionen Und Von Interpolationskoeffizienten. Numerische Mathematik, 20(3): 238–251, 1973

    work page 1973

  32. [32]

    Amir Shpilka, Amir Yehudayoff: Arithmetic Circuits: A Survey of Recent Results and Open Questions. Found. Trends Theor. Comput. Sci. 5(3-4): 207-388 (2010)

    work page 2010

  33. [33]

    Shmuel Winograd: On the Number of Multiplications Needed to Compute Certain Functions. Comm. on Pure and Appl. Math. (23): 165–179, 1970

    work page 1970