Given a group G and two vectors v and w in a representation V, one can ask: do v and w lie in the same orbit? This is what we call the orbit problem. For the action of GLn on m-tuples of n × n matrices, the orbit problem translates to the module isomorphism problem for which there is a known polynomial time algorithm. In joint work with Visu Makam, we also gave a polynomial time algorithm for deciding whether the orbit closures of v and w intersect. We also have similar results for the left-right action of SLn × SLn on the space of m-tuples of matrices. These results are related to interesting problems in algebraic complexity theory, such as non-commutative rational identity testing. The graph isomorphism problem can also formulated as an orbit problem. No polynomial time algorithm for the graph isomorphism problem is known. I will discuss an algorithm for the graph isomorphism problem that is more powerful than the higher-dimensional Weisfeiler-Leman algorithm when it comes to distinguishing pairs of non-isomorphic graphs in polynomial time. (This algorithm could potentially be polynomial time, but we will not make such a bold claim.)
This video was produced by the University of Warwick as part of the 7th Workshop on Algebraic Complexity Theory (WACT) 2023.
