Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries
The determinantal complexity of a polynomial is the order of the smallest matrix whose entries are polynomials of degree at most one and whose determinant equals the polynomial. A lower bound for the permanent in this measure is the algebraic form of the question whether the permanent is harder to compute than the determinant. Over the complex numbers, the best known lower bound grows cubically in the size of the permanent. It holds even when the permanent only has to be a limit of such determinants. I prove that the cubic lower bound holds over every algebraically closed field of odd…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.40484
curl -X POST /api/v1/records/arxiv/2610.40484/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.40484/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'