Polynomial Time Algorithms in Invariant Theory for Torus Actions

An action of a group on a vector space partitions the latter into a set of orbits. We consider three natural and useful algorithmic "isomorphism" or "classification" problems, namely, orbit equality, orbit closure intersection, and orbit closure containment. These capture and relate to a variety of problems within mathematics, physics and computer science, optimization and statistics. In the talk, we show that there are polynomial time algorithms for all three of the aforementioned problems. We also show how to efficiently find separating invariants for orbits, and how to compute systems of generating rational invariants for these actions (in contrast, for polynomial invariants the latter is known to be hard). The talk is based on a joint work with P. Bürgisser, V. Makam, M. Walter and A. Wigderson.