OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
Proves an \Omega(n^3) lower bound for the border determinantal complexity of the n× n permanent over ℂ. Even coefficientwise limits of determinants of affine-linear matrices require matrix size at least cn^3, for an absolute c > 0 and all sufficiently large n; the same bound therefore holds for exact representations.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
A cubic lower bound for border determinantal complexity of the permanent
We prove that the complex border determinantal complexity of the m× m permanent is \Omega(m^3), 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…
Full source abstract
We prove that the complex border determinantal complexity of the m× m permanent is \Omega(m^3), 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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.