让下一篇重要论文，不再错过。

原文摘要

We prove that every fan-in 2 noncommutative arithmetic circuit computing the palindrome polynomial $\mathrm{Pal}_{n,d}(X,Y)$ of degree $2d$ in $2n$ variables has size $Ω(nd)$, which is tight up to a constant. In particular, when $d = n$ we obtain an $Ω(n^2)$ lower bound, improving the previous lower bound of $Ω(n \log n)$ by Nisan and concurrent work of $Ω(n^{1.5})$ by Raz (FOCS 2026). The proof builds on and refines a previous work of the first author, by constructing for every gate a small set that spans a subset of the coefficients of the polynomial computed by that gate. We show that the structure of the set depends only on the subsets of multiplication gates along paths going from that gate to a leaf. From this description, we are then able to get an upper bound on this set based on the amount of product gates in the circuit. The proof is surprisingly short and simple to understand, considering that improving Nisan's $Ω(n \log n)$ lower bound for noncommutative circuits has been an open problem for decades.