A cubic lower bound for the border determinantal complexity of the permanent (beyond the quadratic Mignon-Ressayre barrier)

Theorem 1.1: $\mathrm{bdc}(\mathrm{per}_m)\ge cm^3$ for $m\ge m_0$, with $c=1/(5529600e)$ and $m_0=1408$, over $\mathbb C$ with arbitrary affine-linear entries and coefficientwise limits at fixed size; the same bound holds for $\mathrm{dc}$, and affine-linear algebraic branching programs for $\mathrm{per}_m$ need $\Omega(m^3)$ vertices and edges (also in the border sense at fixed budget). The route is a smooth-hypersurface bound $(r-1)(d-1)/(4e)$ for forms of degree $r$ in $d$ variables, applied to a coefficient polynomial extracted from a permanent. It remains a fixed polynomial bound: superpolynomial $\mathrm{dc}$ or $\mathrm{bdc}$ for the permanent, and VP versus VNP, stay open.

Theorem 1.1: $\mathrm{bdc}(\mathrm{per}_m)\ge cm^3$ for $m\ge m_0$, with $c=1/(5529600e)$ and $m_0=1408$, over $\mathbb C$ with arbitrary affine-linear entries and coefficientwise limits at fixed size; the same bound holds for $\mathrm{dc}$, and affine-linear algebraic branching programs for $\mathrm{per}_m$ need $\Omega(m^3)$ vertices and edges (also in the border sense at fixed budget). The route is a smooth-hypersurface bound $(r-1)(d-1)/(4e)$ for forms of degree $r$ in $d$ variables, applied to a coefficient polynomial extracted from a permanent. It remains a fixed polynomial bound: superpolynomial $\mathrm{dc}$ or $\mathrm{bdc}$ for the permanent, and VP versus VNP, stay open.