Article
Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
Author/s | Briand, Emmanuel
Orellana, Rosa C. Rosas Celis, Mercedes Helena |
Department | Universidad de Sevilla. Departamento de álgebra |
Publication Date | 2009-12 |
Deposit Date | 2016-05-30 |
Published in |
|
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 ... 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. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España Junta de Andalucía |
Project ID. | info:eu-repo/grantAgreement/MINECO/MTM2007–64509
FQM333 |
Citation | Briand, E., Orellana, R.C. y Rosas Celis, M.H. (2009). Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH. Computational complexity, 18 (4), 577-600. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Reduced Kronecker coefficients ... | 288.6Kb | [PDF] | View/ | |