Complexity and Completeness of Immanants
By Jean-Luc Brylinski, Ranee Brylinski. 2003
13 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- Determinantal Point Processes for Machine Learning (2012, background): “Complexity results for immanants are less definitive, with certain classes of immanants apparently hard to compute [19, 20], while some upper bounds on complexity are known [5, 65], and at least one nontrivial case is efficiently computable [62].”