Colloquium: Greta Panova, University of Southern California

Quantum and classical complexity in algebraic combinatorics.

Algebraic combinatorics studies discrete structures and
integer quantities arising from algebra, representation theory and
algebraic geometry. Finding formulas and understanding their behavior
is a major goal following the foundational breakthroughs of results
like the hook-length formula giving the dimensions of irreducible
symmetric group modules, or the Littlewood-Richardson rule for
multiplicities of irreducible GL representations in tensor products.
Yet many other such problems remain unanswered in a satisfactory way.
A way to explain this phenomenon is to formalize the existence of such
solutions via the concepts of computational complexity theory. In the
opposite direction, such quantities play key roles in determining
lower bounds in algebraic complexity theory aiming to prove VP \neq
VNP and ultimately P\neq NP. They also appear natural to quantum
computation and can serve as testing grounds for establishing quantum
vs classical speedups.