A Quadratic Lower Bound for Noncommutative Circuits

We prove that every fan-in $2$ noncommutative arithmetic circuit computing the palindrome polynomial has size $\mathrm{\Omega }(nd)$. In particular, when $d=n$ we obtain an $\mathrm{\Omega }(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.