A cubic lower bound for border determinantal complexity of the permanent
We prove that the complex border determinantal complexity of the $m\times 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.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent
curl -X POST /api/v1/records/openai-math/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
The MathocalypseShtetl-OptimizedOct 7, 2026
improving the previous best bound which was quadratic. A randomized polytime algorithm to approximately count the number of perfect matchings in a general graph, as well as a randomized nearly linear-time algorithm for finding a maximum matching in such a graph A deterministic polynomial-time…