| Abstrakt: |
We study the complexity of computing Kronecker coefficients $${g(\lambda,\mu,\nu)}$$ . We give explicit bounds in terms of the number of parts $${\ell}$$ in the partitions, their largest part size N and the smallest second part M of the three partitions. When M = O(1), i.e., one of the partitions is hook-like, the bounds are linear in log N, but depend exponentially on $${\ell}$$ . Moreover, similar bounds hold even when $${M=e^{O(\ell)}}$$ . By a separate argument, we show that the positivity of Kronecker coefficients can be decided in O(log N) time for a bounded number $${\ell}$$ of parts and without restriction on M. Related problems of computing Kronecker coefficients when one partition is a hook and computing characters of S are also considered. [ABSTRACT FROM AUTHOR] |
Full text from SpringerLink