| March 03, 13:00

Kronecker coefficients, moment polytopes, and computational complexity

Michael Walter

The Kronecker coefficients are among the most fascinating objects in classical representation theory. While many of their fundamental properties remain mysterious, the past decade has brought some significant advances, in part through new and surprising connections to quantum physics and computational complexity theory. In this talk, I will give an introduction to this subject and its motivations, and discuss some recent results. Specifically, I will explain that the problem of deciding positivity of Kronecker coefficients is NP-hard in general, while their asymptotic non-vanishing, as encoded by certain moment polytopes, can be decided in NP and coNP (arXiv:1410.8144, 1507.02955, 1511.03675). This is in marked contrast to celebrated results on the Littlewood-Richardson coefficients and the Horn inequalities, and it suggests that representation theory can be strictly easier in the asymptotic regime. Lastly, and somewhat counter-intuitively, our hardness result can be turned into an efficient algorithm for studying the failure of the saturation property for Kronecker coefficients, which is at present only poorly understood.


Stanford University
Seminarroom 0.02, ETP
Contact: not specified