Codes and Expansions (CodEx) Seminar

Harm Derksen (Northeastern University):
Invariant Theory and Complexity

We will consider questions about orbits for an action of a group on a vector space by linear transformation. Examples of such orbit problems are, deciding whether two elements in the vector space lie in the same orbit, or whether one orbit is contained in the closure of the other orbit. Many important problems, such as the Graph Isomorphism Problem can be formulated in this way. I will discuss various situations where these problems can be solved efficiently. There are also interesting connections to Complexity Theory.