Reduced Kronecker coefficients and counter-examples to Mulmuley's saturation conjecture SH
Preprint
Abstract
We provide counter-examples to Mulmuley's SH conjecture for the Kronecker coefficients. This conjecture was proposed in the setting of Geometric Complexity Theory to show that deciding whether or not a Kronecker coefficient is zero can be done in polynomial time. We also provide a short proof of the #P-hardness of computing the Kronecker coefficients. Both results rely on the connections between the Kronecker coefficients and another family of structural constants in the representation theory of the symmetric groups: Murnaghan's reduced Kronecker coefficients.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- On the complexity of computing Kostka numbers and Littlewood-Richardson coefficientsJournal of Algebraic Combinatorics, 2006
- A polynomiality property for Littlewood–Richardson coefficientsJournal of Combinatorial Theory, Series A, 2004
- The Kronecker Product of Schur Functions Indexed by Two-Row Shapes or Hook ShapesJournal of Algebraic Combinatorics, 2001
- The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjectureJournal of the American Mathematical Society, 1999
- Stability of Kronecker Products of Irreducible Characters of the Symmetric GroupThe Electronic Journal of Combinatorics, 1999
- Residue formulae, vector partition functions and lattice points in rational polytopesJournal of the American Mathematical Society, 1997
- On the Kronecker product of Schur functions of two row shapesBulletin of the Belgian Mathematical Society - Simon Stevin, 1994
- Products and Plethysms of Characters with Orthogonal, Symplectic and Symmetric GroupsCanadian Journal of Mathematics, 1958