Joint Colloquium/Combinatorics Colloquium: Computational Complexity in Algebraic Combinatorics
- Sponsor
- Colloquium, Combinatorics Colloquium
- Speaker
- Greta Panova (U. Southern California)
- Contact
- Alexander Yong
- ayong@illinois.edu
- Views
- 47
- Originating Calendar
- Mathematics Seminar Series: Combinatorics
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.