Repositorio de producción científica de la Universidad de Sevilla

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

 

Advanced Search
 
Opened Access Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
Cites

Show item statistics
Icon
Export to
Author: Briand, Emmanuel
Orellana, Rosa C.
Rosas Celis, Mercedes Helena
Department: Universidad de Sevilla. Departamento de álgebra
Date: 2009-12
Published in: Computational complexity, 18 (4), 577-600.
Document type: Article
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.
Cite: 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.
Size: 288.6Kb
Format: PDF

URI: http://hdl.handle.net/11441/41677

DOI: 10.1007/s00037-009-0279-z

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)