CCApr 22
A Quadratic Lower Bound for Noncommutative Circuits
arXiv:2604.205759.8
AI Analysis
This is an incremental theoretical advance in computational complexity, addressing lower bounds for noncommutative circuits.
The paper tackles the problem of proving a size lower bound for noncommutative arithmetic circuits computing the palindrome polynomial, and the result is a quadratic lower bound of Ω(n²) for fan-in 2 circuits.
We prove that every fan-in $2$ noncommutative arithmetic circuit computing the palindrome polynomial has size $Ω(n^2)$. The proof builds on and refines a previous work of the author. The new ingredients in the proof were generated by Gemini 3.1 Pro.