Speaker: Greta Panova
University of Southern California
Will give a Colloquium entitled:
Computational Complexity in Algebraic Combinatorics
Abstract: Algebraic Combinatorics studies objects and quantities originating in Algebra, Representation Theory and Algebraic Geometry via combinatorial methods, finding formulas and neat interpretations. Some of its feats include the hook-length formula for the dimension of an irreducible symmetric group ($S_n$) module, or the Littlewood-Richardson rule to determine multiplicities of GL irreducibles in tensor products. Yet some natural multiplicities elude us, among them the fundamental Kronecker coefficients for the decomposition of tensor products of $S_n$ irreducibles, and the plethysm coefficients for compositions of GL modules. Answering those questions could help Geometric Complexity Theory towards establishing lower bounds for the far-reaching goal to show that $P \neq NP$. We will discuss how Computational Complexity Theory provides a theoretical framework for understanding what kind of formulas or rules we could have. As a proof of concept we show that the square of a symmetric group character could not have a combinatorial interpretation. Based on joint works with Christian Ikenmeyer and Igor Pak.
Date: 02-19-2024
Time: 4:00 pm
Location: 129 Hayes-Healy Bldg
Zoom URL: https://notredame.zoom.us/j/99986867672?pwd=Z2NJRlZwL0dTR0Nxbk50NElHK0dNdz09