Lower Bounds Against Non-Commutative Models of Algebraic Computation
summary
Proves a concrete improvement: any homogeneous non-commutative circuits computing the ordered elementary symmetric polynomial of degree n/2 requires size Ω(n^2), beating the classical Baur–Strassen Ω(n log n) bound. Method defines position-aware partial derivatives, uses a rank measure over the position-restricted derivatives and a homogeneous version of the Baur–Strassen simultaneous-derivatives trick to translate small circuit size into low rank; constructs the polynomial explicitly and the argument succeeds.
AI-written summary · about