Mathematics

Computational complexity meets algebraic combinatorics

Greta Panova (University of Southern California)

Abstract: How hard is a problem? How nice is a solution? Such questions can actually be formalized using the theory of Computational Complexity. Yet, distinguishing the different computational complexity classes, like P vs NP, are major problems. Algebraic Combinatorics studies discrete structures originating in Algebra/Representation Theory via combinatorial methods and vice versa. Some of the main longstanding open problems concern the “combinatorial interpretation” of structure constants and multiplicities originally defined via representation theory like Kronecker and plethysm coefficients. In this talk we will discuss the two-way interaction between the fields via such structure constants. First, how Kronecker coefficients appear in the distinction of algebraic complexity classes via the Geometric Complexity Theory. Second, how computational complexity explains why the problem of finding a combinatorial interpretation is hard.

Meeting Info: please email ayong@illinois.edu