A Quadratic Lower Bound for Noncommutative Circuits

Abstract

We prove that every fan-in $2$ noncommutative arithmetic circuit computing the palindrome polynomial has size $\hat{I}\text{c◯}(nd)$. In particular, when $d=n$ we obtain an $\hat{I}\text{c◯}(n^2)$ lower bound. The proof builds on and refines a previous work of the author. Key ideas in the proof were generated by Gemini 3.1 Pro.

9 pages. Improved parametrization, proof now works for small d