2026-07-23T15:11:24Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:14278
2024-03-06T10:53:51Z
ddc:004
open_access
A Lower Bound on Determinantal Complexity
Kumar, Mrinal
Volk, Ben Lee
Determinantal Complexity
Algebraic Circuits
Lower Bounds
Singular Variety
The determinantal complexity of a polynomial P β π½[xβ, β¦, x_n] over a field π½ is the dimension of the smallest matrix M whose entries are affine functions in π½[xβ, β¦, x_n] such that P = Det(M). We prove that the determinantal complexity of the polynomial β_{i = 1}^n x_i^n 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 [Jarod Alper et al., 2017] for the same polynomial.
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
Mrinal Kumar and Ben Lee Volk
2021
Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.CCC.2021.4
urn:nbn:de:0030-drops-142781
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.4
eng
https://creativecommons.org/licenses/by/4.0/legalcode