{"id":"arxiv/2609.34462","url":"https://arxiv.org/abs/2609.34462","tags":["cs.CC","math.AC","math.AG"],"score":0,"title":"A Quadratic Lower Bound on Determinantal Complexity","domain":"cs.CC","source":"arxiv","authors":["Mrinal Kumar","Ben Lee Volk"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}