Computer Science/Discrete Mathematics Seminar II

This (mostly expository) talk will be about invariant theory viewed through the lens of computational complexity. Invariant theory is the study of symmetries, captured by group actions, by polynomials that are “invariant.” Invariant theory has had a deep and lasting influence in mathematics. In fact, Lie theory and algebraic geometry, differential algebra and algebraic combinatorics are all offsprings of invariant theory. In our century, exciting connections between invariant theory and fundamental problems in complexity (such as P vs NP) have been uncovered thanks to the Geometric Complexity Theory program. I will discuss various topics such as degree bounds, null cones, orbits and their closures, and also mention more recent results on non-commutative identity testing. There will be many examples, and the goal is to familiarize the audience with the problems, goals and techniques of interest as well as the connections with complexity. This talk is intended to provide motivation, background, and context for the talk next week. No special background will be assumed.