Quadratic lower bound found for complexity of power sum polynomials
A Quadratic Lower Bound on Determinantal Complexity
Computational Complexity
Summary
Determining how complex a polynomial is can be very challenging. The authors show that at least a certain large level of complexity, proportional to the square of the size of the input, is necessary for a key polynomial called the power sum polynomial. They provide a simpler and clearer proof compared to a previous more complicated, AI-assisted claim. This helps clarify an important fundamental question in algebraic complexity theory.
What this means in practice
- •For complexity theorists: Clarify limitations when representing certain polynomials efficiently in algebraic complexity studies.
- •For cryptography engineers: Inform cryptographic system designs that rely on hardness assumptions related to polynomial representations.
A theory result. No direct application yet.
Authors
Mrinal Kumar, Ben Lee Volk
Abstract
We prove an $Ω(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over the field of complex numbers. A similar result was claimed in a recent paper of Sheshadri (arXiv:2606.13628), via an AI-assisted and AI-written proof. Assuming its correctness, this was the first super-linear lower bound for this fundamental algebraic problem for any explicit polynomial. However, the authors of this note were unable to follow the details and verify the argument in arXiv:2606.13628, in spite of considerable effort on their part. The proof we provide here is short, (almost) self-contained and seemingly simpler.