pith. sign in

arxiv: cs/0301024 · v2 · submitted 2003-01-23 · 💻 cs.CC · math.CO

Complexity and Completeness of Immanants

classification 💻 cs.CC math.CO
keywords immanantsattachedcomputationdeltadiagramspermanentsseparationvnp-complete
0
0 comments X
read the original abstract

Immanants are polynomial functions of n by n matrices attached to irreducible characters of the symmetric group S_n, or equivalently to Young diagrams of size n. Immanants include determinants and permanents as extreme cases. Valiant proved that computation of permanents is a complete problem in his algebraic model of NP theory, i.e., it is VNP-complete. We prove that computation of immanants is VNP-complete if the immanants are attached to a family of diagrams whose separation is $\Omega(n^\delta)$ for some $\delta>0$. We define the separation of a diagram to be the largest number of overhanging boxes contained in a single row. Our theorem proves a conjecture of Buergisser for a large variety of families, and in particular we recover with new proofs his VNP-completeness results for hooks and rectangles.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.