Computational Complexity in Algebraic Combinatorics, Greta Panova (University of Southern California) -- March 21st, 2024, 4:00pm in Altgeld 245 (Combinatorics/Department Colloquium)

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.

The seminar co-organizers are Ian Cavey, Andrew Hardt, Shiliang Gao, Elizabeth Kelley, and Alexander Yong.