Greta Panova, USC

Abstract: How hard is it to solve a problem? A formal answer can be given by Computational Complexity theory where the "easy" problems are, generally speaking, in the classes P, FP, VP (algebraic version) and the hard ones in NP, #P, VNP. Yet, the biggest open problem there, to prove P \neq NP, and the algebraic VP \neq VNP, are widely open.
Algebraic Combinatorics studies discrete objects and multiplicities coming from Representation Theory and Algebraic Geometry. Some of the major and long standing open problems concern the "combinatorial interpretation" (positive formula) for the Kronecker coefficients of Sn, telling us how tensor products of irreducibles factor, and for the plethysm coefficients of GLn telling us how compositions of irreducibles factor.
These two, seemingly disjoint areas of research, come together in two ways: the Kronecker and plethysm coefficients play a crucial role in the Geometric Complexity Theory program aimed at proving VP \neq VNP. In the opposite direction, Computational Complexity Theory can tell us exactly how hard the major open problems in Algebraic Combinatorics are. We can demonstrate this with a recent advancement -- squares of the Sn character are not in #P (and hence do not have a combinatorial interpretation).