Pith. sign in

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

arxiv 2009.02452 v2 pith:LHJEPE7E submitted 2020-09-05 cs.CC math.AG

A Lower Bound on Determinantal Complexity

classification cs.CC math.AG
keywords polynomialboundcomplexitydeterminantallowermathbbldotsleast
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A near-quadratic lower bound on the border determinantal complexity of $\sum_i x_i^n$ via conormal specialization

    cs.CC 2026-06 unverdicted novelty 8.0

    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.

  2. A symmetric determinantal lower bound for diagonal power sums via polar degree

    cs.CC 2026-06 unverdicted novelty 6.0

    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.