A full complexity dichotomy for immanant families

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstrakt

Given an integer n ≥ 1 and an irreducible character χλ of Sn for some partition λ of n, the immanant immλ:ℂn× n→ℂ maps matrices A∈ℂn× n to immλ(A)=∑π∈ Snχλ(π)∏i=1nAi,π(i). Important special cases include the determinant and permanent, which are obtained from the sign and trivial character, respectively.

It is known that immanants can be evaluated in polynomial time for characters that are “close” to the sign character: Given a partition λ of n with s parts, let b(λ):=n−s count the boxes to the right of the first column in the Young diagram of λ. For a family of partitions Λ, let b(Λ) := maxλ∈Λb(λ) and write Imm(Λ) for the problem of evaluating immλ(A) on input A and λ∈Λ. On the positive side, if b(Λ)<∞, then Imm(Λ) is known to be polynomial-time computable. This subsumes the case of the determinant. Conversely, if b(Λ)=∞, then previously known hardness results suggest that Imm(Λ) cannot be solved in polynomial time. However, these results only address certain restricted classes of families Λ.

In this paper, we show that the assumption FPT≠ #W[1] from parameterized complexity rules out polynomial-time algorithms for Imm(Λ) for any computationally reasonable family of partitions Λ with b(Λ)=∞. We give an analogous result in algebraic complexity under the assumption VFPT≠ VW[1]. Furthermore, if b(λ) even grows polynomially in Λ, we show that Imm(Λ) is hard for #P and VNP. This concludes a series of partial results on the complexity of immanants obtained over the last 35 years.
OriginalsprogEngelsk
TitelProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Antal sider14
ForlagAssociation for Computing Machinery
Publikationsdato15 jun. 2021
Sider1770
DOI
StatusUdgivet - 15 jun. 2021

Fingeraftryk

Dyk ned i forskningsemnerne om 'A full complexity dichotomy for immanant families'. Sammen danner de et unikt fingeraftryk.

Citationsformater