Family 108Theoretical computer scienceNo LeanNot yet digested
A cubic permanent–determinant lower bound
Proves an lower bound for the border determinantal complexity of the permanent over ℂ. Even coefficientwise limits of determinants of affine-linear matrices require matrix size at least , for an absolute c > 0 and all sufficiently large n; the same bound therefore holds for exact representations.
Manuscripts in this family · 1
A cubic lower bound for border determinantal complexity of the permanent
Sep 24, 2026·A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026.pdf
We prove that the complex border determinantal complexity of the permanent is , allowing arbitrary affine-linear determinant representations and coefficientwise limits. It also gives cubic lower bounds for exact determinantal complexity and for the numbers of vertices and edges in affine-linear algebraic branching programs, including coefficientwise limits with a fixed vertex or edge budget.