Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-218 | 28th September 2026 14:30

A Quadratic Lower Bound on Determinantal Complexity

RSS-Feed




TR26-218
Authors: Mrinal Kumar, Ben Lee Volk
Publication: 28th September 2026 14:53
Downloads: 95
Keywords: 


Abstract:

We prove an $\Omega(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, 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 Sheshadri's proof in spite of considerable effort on their part.

The proof we provide here is short, (almost) self-contained and seemingly simpler.

\textbf{AI Use: }ChatGPT Astra was used by the authors on multiple occasions to parse through some of the parts of Sheshadri's proof in [Shesh2026] and the outline of the proof in this note came out of this exercise. The final exposition as well as some of the final details in this note are due to its human authors.



ISSN 1433-8092 | Imprint