Computing Multiplicities of Lie Group Representations

TY - GEN

T1 - Computing Multiplicities of Lie Group Representations

AU - Christandl, Matthias

AU - Doran, Brent

AU - Walter, Michael

N1 - Conference code: 53

PY - 2012

Y1 - 2012

N2 - For fixed compact connected Lie groups H ⊆ G, we provide a polynomial time algorithm to compute the multiplicity of a given irreducible representation of H in the restriction of an irreducible representation of G. Our algorithm is based on a finite difference formula which makes the multiplicities amenable to Barvinok's algorithm for counting integral points in polytopes. The Kronecker coefficients of the symmetric group, which can be seen to be a special case of such multiplicities, play an important role in the geometric complexity theory approach to the P vs. NP problem. Whereas their computation is known to be #P-hard for Young diagrams with an arbitrary number of rows, our algorithm computes them in polynomial time if the number of rows is bounded. We complement our work by showing that information on the asymptotic growth rates of multiplicities in the coordinate rings of orbit closures does not directly lead to new complexity-theoretic obstructions beyond what can be obtained from the moment polytopes of the orbit closures. Non-asymptotic information on the multiplicities, such as provided by our algorithm, may therefore be essential in order to find obstructions in geometric complexity theory.

AB - For fixed compact connected Lie groups H ⊆ G, we provide a polynomial time algorithm to compute the multiplicity of a given irreducible representation of H in the restriction of an irreducible representation of G. Our algorithm is based on a finite difference formula which makes the multiplicities amenable to Barvinok's algorithm for counting integral points in polytopes. The Kronecker coefficients of the symmetric group, which can be seen to be a special case of such multiplicities, play an important role in the geometric complexity theory approach to the P vs. NP problem. Whereas their computation is known to be #P-hard for Young diagrams with an arbitrary number of rows, our algorithm computes them in polynomial time if the number of rows is bounded. We complement our work by showing that information on the asymptotic growth rates of multiplicities in the coordinate rings of orbit closures does not directly lead to new complexity-theoretic obstructions beyond what can be obtained from the moment polytopes of the orbit closures. Non-asymptotic information on the multiplicities, such as provided by our algorithm, may therefore be essential in order to find obstructions in geometric complexity theory.

U2 - 10.1109/FOCS.2012.43

DO - 10.1109/FOCS.2012.43

M3 - Article in proceedings

SN - 978-1-4673-4383-1

SP - 639

EP - 648

BT - 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - IEEE 53rd Annual Symposium on Foundations of Computer Science

Y2 - 20 October 2012 through 23 October 2012

ER -