Solution to an open problem on the computational complexity of immanant
Immanants are a class of generalized matrix functions associated with the irreducible characters of the symmetric group. Bürgisser [SIAM J. Comput., 30 (2000), pp. 1023--1040] proved that the computation of hook immanants and immanants corresponding to rectangular Young diagrams of polynomially growing width is VNP-complete under $p$-projections. And he posed an open problem: whether the family of immanants corresponding to rectangular Young diagrams of width $2$ is VNP-complete under $p$-projections. This paper gives a solution to this problem. We prove that, over any field of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.24045
curl -X POST /api/v1/records/arxiv/2608.24045/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.24045/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'