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.
