Noncommutative circuits after the 2026 quadratic: the palindrome bound Ω(n²) is tight — an n^{1.19} bound at constant degree would amplify to exponential

Record

Ω(nd) for every fan-in-2 noncommutative circuit computing the palindrome polynomial Pal_{n,d} — Ω(n²) at d = n, tight since Pal has O(nd) circuits (arXiv preprint, 2026, superseding the Ω(n log n) that stood since Baur–Strassen); peer-reviewed records: Ω(n^{1+c}) under syntactic degree O(n) (ITCS 2026) and Ω(nd) for homogeneous circuits (CCC 2023); formulas/ABPs: exponential since Nisan 1991

Record held by

Shastri, arXiv:2604.20575 (2026, preprint, v3); Shastri, \"Lower Bounds for Noncommutative Circuits with Low Syntactic Degree\", ITCS 2026; Chatterjee & Hrubeš, CCC 2023 (ECCC TR23-001); Nisan, STOC 1991

Hardness

the published threshold: any explicit constant-degree noncommutative polynomial requiring circuits of size Ω(n^{ω/2+ε}) — i.e. about n^{1.19} with current ω — already implies explicit exponential exp(m^c) lower bounds; superlinear at constant degree thus means exponential noncommutative bounds or ω = 2

Hardness from

Carmosino, Impagliazzo, Lovett & Mihajlin, CCC 2018 (ECCC TR18-095, \"Hardness Amplification for Non-Commutative Arithmetic Circuits\")

Endgame

the CILM amplifier is the loop: Ω(n^{ω/2+ε}) for an explicit constant-degree noncommutative polynomial yields explicit families requiring exp(m^c)-size noncommutative circuits (Theorem 1.2, CCC 2018), and poly-degree bounds beyond n^{ω/2+ε} lift to arbitrary polynomial bounds (Theorem 1.1); a noncommutative determinant in poly size would even give VP = VNP (Arvind–Srinivasan, cited there)

Problems

Noncommutative Arithmetic Circuits, Palindrome Polynomial, Arithmetic Circuit Lower Bounds

Statement

Two targets, in order of the amplifier. (1) Beat the record polynomial-degree bound: an explicit 2n-variate noncommutative polynomial requiring circuits of size ω(n²) — the palindrome bound Ω(nd) is exactly tight for the palindrome, so this needs a new hard polynomial. (2) The loop-closing target: any explicit constant-degree noncommutative polynomial requiring size Ω(n^{ω/2+ε}) ≈ n^{1.19}; by Carmosino–Impagliazzo–Lovett–Mihajlin this amplifies to exponential lower bounds, which is why nothing superlinear is known at constant degree.

Current record

Nisan (STOC 1991) proved exponential lower bounds for noncommutative formulas and ABPs (2^{Ω(n)} for permanent and determinant), but circuits stayed at Ω(n log n) for over three decades. Movement came 2023–2026: Chatterjee and Hrubeš (CCC 2023) proved Ω(nd) for homogeneous circuits; Shastri (ITCS 2026) generalized to circuits of syntactic degree O(n), getting Ω(n^{1+c}); and in April 2026 Shastri (arXiv:2604.20575, still a preprint — the paper notes its key ideas were generated by Gemini 3.1 Pro) removed all restrictions, proving every fan-in-2 noncommutative circuit computing Pal_{n,d}(X,Y) has size Ω(nd), quadratic at d = n. The proof bounds the dimension of a coefficient space against spanning sets parameterized by strictly-decreasing syntactic degree classes. Concurrent unpublished work of Raz (cited in Shastri's Section 2) proves Ω(d√n) and connects such bounds to circuits over free noncommutative rings. The bound is tight for the palindrome, which has O(nd) homogeneous circuits.

Why it matters

Noncommutativity is supposed to be the easy case — cancellation, the engine of upper bounds, is crippled — yet circuit lower bounds trail formulas by an exponential. CILM (CCC 2018) explains and weaponizes this: the model has a threshold at n^{ω/2}, so the gap between the new quadratic (at degree n) and n^{1.19} (at degree O(1)) is the entire distance to exponential bounds. A constant-degree superlinear bound would also decide a dichotomy: either exponential noncommutative lower bounds exist, or ω = 2 (superlinear bounds would refute themselves otherwise) — either outcome is major.

Attack surface

The degree regime is the whole game: Shastri's spanning-set argument fundamentally spends the degree (parameterizations of length r ≤ d), so at d = O(1) it returns nothing — porting the coefficient-space viewpoint to constant degree is the direct attack. Candidate hard polynomials at constant degree: CILM's own encoded families E(f) (their variable-compression preserves hardness, so one can search low-variable images of known hard polynomials), and the degree-4 width-hardness polynomials of Hrubeš–Wigderson–Yehudayoff (STOC 2010), whose sum-of-squares connection is an independent published route to exponential bounds. Above degree n, beating Ω(n²) needs a polynomial with larger coefficient span than the palindrome — Pal is tight, so try IMM-style words. Cheap first experiment: verify whether the Ω(d√n) of Raz's concurrent manuscript composes with CILM's encoding at r = 3 to beat n^{ω/2} in any parameter range.

Verification notes

Checked August 2026: the unrestricted quadratic bound (arXiv:2604.20575) is a preprint, v3 dated May 18, 2026; its intro and independent 2026 papers confirm Ω(n log n) was the prior unrestricted record. CILM thresholds read from ECCC TR18-095 directly (Theorems 1.1–1.2).