REVIEW 2 cited by
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
A Lower Bound on Determinantal Complexity
read the original 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.
Forward citations
Cited by 2 Pith papers
-
A near-quadratic lower bound on the border determinantal complexity of $\sum_i x_i^n$ via conormal specialization
The border determinantal complexity of sum_{i=1}^n x_i^n is at least (n-1)^2/(4e) and the symmetric version at least (n-1)^2/(2e) for n>=3 over the complexes.
-
A symmetric determinantal lower bound for diagonal power sums via polar degree
Proves sdc(sum x_i^n) >= (1/(2e) - o(1)) n^2 over C using polar degree of the associated hypersurface and multihomogeneous Bezout on an incidence variety after symmetric Schur complement.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.