Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH

Abstract

We provide counter-examples to Mulmuley's strong saturation conjecture (strong SH) 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. An appendix by Mulmuley introduces a relaxed form of the saturation hypothesis SH, still strong enough for the aims of Geometric Complexity Theory.

25 pages. With an appendix by Ketan Mulmuley. To appear in Computational Complexity. See also http://emmanuel.jean.briand.free.fr/publications/

References in corpus (7)

• Quantum marginal problem and representations of the symmetric group
• The stability of the Kronecker products of Schur functions
• Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
• Geometric Complexity Theory VII: Nonstandard quantum group for the plethysm problem
• Geometric Complexity III: on deciding positivity of Littlewood-Richardson coefficients
• Geometric Complexity Theory VIII: On canonical bases for the nonstandard quantum groups
• On P vs. NP, Geometric Complexity Theory, and the Flip I: a high level view

Cited by in corpus (21)

• The stability of the Kronecker products of Schur functions
• Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
• Proof of Stembridge's conjecture on stability of Kronecker coefficients
• An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP
• On the complexity of computing Kronecker coefficients
• Symmetric group characters as symmetric functions
• Kronecker products, characters, partitions, and the tensor square conjectures
• Plethysm and lattice point counting
• Permanent versus determinant: not via saturations
• Bounds on the Kronecker coefficients
• Multiplicity of compact group representations and applications to Kronecker coefficients
• Rectangular symmetries for coefficients of symmetric functions
• Vector partition functions and Kronecker coefficients
• Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
• The co-Pieri rule for Kronecker coefficients
• On the growth of the Kronecker coefficients
• All Kronecker coefficients are reduced Kronecker coefficients
• Breaking down the reduced Kronecker coefficients
• Report on "Mathematical Aspects of P vs. NP and its Variants."
• Necessary conditions for the positivity of Littlewood-Richardson and plethystic coefficients
• Combinatorics on several families of Kronecker coefficients related to plane partitions