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.