complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

Question

The fermionant is a matrix function from physics, which is indexed by a positive integer $k$:

\begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A). \end{align}

In the above $A$ is an $n \times n$ matrix, $\lambda$ ranges over all partitions of $n$ with at most $k$ parts, $\lambda^T$ is the transpose of the partition $\lambda$, $d_{\lambda}^{(k)}$ is the number of semi-standard Young tableaux of shape $\lambda$ and content $\{1,2,\dots k \}$, and $\operatorname{Imm}_{\lambda}(A)$ is the $\lambda$-immanant of the matrix $A$.

In S. Mertens and C. Moore "The complexity of the fermionant and immanants of constant width"(2013), it is shown for $k=2$ that $\operatorname{Ferm}_k$ is in the class $\oplus \bf{P}$.

In the above-mentioned paper, it is said that:

If $k=\mathcal{O}(1)$, there are $\mathcal{O}(n^{k-1})=\operatorname{poly}(n)$ partitions of width $k$ or less. Thus for any constant $k$ there is a polynomial-time Turing reduction from the fermionant $\operatorname{Ferm}_k$ to the problem of computing the immanant $\operatorname{Imm}_{\lambda}$ where $\lambda$ is given as part of the input and where $\lambda$ has width at most $k$. It follows that the problem of computing $\operatorname{Imm}_{\lambda}(A)$ as a function of $A$ and $\lambda$ is $\oplus \bf{P}$ under polynomial-time Turing reductions if $k=2$. In particular, unless the polynomial hierarchy collapses, there exits partitions $\lambda$ of width $2$ such that $\operatorname{Imm}_{\lambda}(A)$ is not in $\bf{P}$.

I am interested in the computational complexity of group functions $\mathcal{D}^{\lambda}_{i,j}$ - these functions are the entries in an irreducible matrix representation of $GL_n$ of type $\lambda$. There is a well-known way of relating group functions and immanants:

\begin{align} \operatorname{Imm}_{\lambda}(A) = \sum_{i=1}^{s_{\lambda}} \mathcal{D}^{\lambda}_{i,i}. \end{align}

My question is as follows. Are the claims that the above-mentioned paper makes also true for group functions? In other words, is it correct to say that the problem of computing a group function $\mathcal{D}^{\lambda}_{i,i}$ is $\oplus \bf{P}$ under polynomial-time Turing reductions if $k=2$; in particular, unless the polynomial hierarchy collapses, there exits partitions $\lambda$ of width $2$ such that $\mathcal{D}^{\lambda}_{i,i}$ is not in $\bf{P}$?

Answer 1

This doesn't quite answer your question because you're asking specifically about diagonal entries (in what basis? Any basis will work for the connection to immanents, but the complexity could change depending on what basis you use to actually compute $D_{ii}^\lambda$), but it's a little too long for a comment.

Bürgisser showed that $(g,v) \mapsto D^{\lambda}(g)\cdot v$ on $GL_m \times \mathbb{C}^m$ can be computed in $poly(m,d_{\lambda},\log|\lambda|, mult(\lambda))$ arithmetic operations, where $mult(\lambda)$ is the maximum multiplicity of restriction between any nodes two levels apart in the Gelfand-Tsetlin graph of $\lambda$. Can be found as Theorem 6.6 in his book Completeness & Reductions.

In Theorem 6.9 he shows that the dependence on $d_\lambda$ is unavoidable.