Name
Abstract | ||
|---|---|---|
The 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.4230/LIPIcs.CCC.2021.4 | CCC |
DocType | Volume | Citations |
Conference | 27 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar | 1 | 37 | 7.11 |
| Ben Lee Volk | 2 | 12 | 5.62 |