ECCC-Report TR20-129https://eccc.weizmann.ac.il/report/2020/129Comments and Revisions published for TR20-129en-usSat, 05 Sep 2020 06:25:44 +0300
Paper TR20-129
| A Lower Bound on Determinantal Complexity |
Mrinal Kumar,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2020/129The determinantal complexity of a polynomial $P \in \mathbb{F}[x_1, \ldots, x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1, \ldots, x_n]$ such that $P = Det(M)$. We prove that the determinantal complexity of the polynomial $\sum_{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 [ABV17] for the same polynomial.
Sat, 05 Sep 2020 06:25:44 +0300https://eccc.weizmann.ac.il/report/2020/129