2020/09/05 by Mrinal Kumar, Kumar, Mrinal, Ben Lee Volk +1 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algebraic Geometry (math.AG) #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation
paper · doi:10.48550/arxiv.2009.02452
openalex publication_date 2020/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The determinantal complexity of a polynomial P ∈ \mathbbF[x1, …, xn] over a field \mathbbF is the dimension of the smallest matrix M whose entries are affine functions in \mathbbF[x1, …, xn] such that P = Det(M). We prove that the determinantal complexity of the polynomial ∑i = 1n xin is at least 1.5n - 3. For every n-variate polynomial of degree d, the determinantal complexity is trivially at least d, and it is a long standing open problem to prove a lower bound which is super linear in max\n,d\. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than max\n,d\, and improves upon the prior best bound of n + 1, proved by Alper, Bogart and Velasco [ABV17] for the same polynomial.