Computer Science/Discrete Mathematics Seminar II

Invariant theory studies the actions of groups on vector spaces and what polynomial functions remain invariant under these actions. An important object related to a group action is the null cone, which is the set of common zeroes of all homogeneous invariant polynomials. I will talk about the structural aspects of the null cone from a computational and optimization perspective. These will include the Hilbert-Mumford and Kempf-Ness theorems which imply that null cone membership is in NP intersect coNP (ignoring bit-size issues). I will explain how this should be thought of as a noncommutative generalization of linear programming duality, which arises when the group is commutative (group of invertible diagonal matrices aka algebraic tori).