Ankit Garg

Microsoft Research

October 10, 2017

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).