Efficient algorithms for geometric invariant theory
MiniSymposium MS125 at the SIAM Conference on Applied Algebraic Geometry 2019, July 12, 2019. Room F107 @ Unitobler, Bern.
Invited Speakers: Harm Derksen, Cole Franks, Ankit Garg, Gábor Ivanyos
Organizers: Peter Bürgisser, Michael Walter
Overview
Recently, motivated by the polynomial identity testing problem from computer science, and by questions arising in quantum information theory, efficient numerical algorithms for solving the null cone problem from geometric invariant theory have been proposed. The goal of the minisymposium is to review this progress and to report on recent advances.
Schedule
Time  Speaker  Title  

10:00–10:30  Harm Derksen  Algorithms for the separation of orbits of matrices  [pdf] 
10:30–11:00  Ankit Garg  Analytic algorithms for the null cone problem  [pdf] 
11:00–11:30  Gábor Ivanyos  Noncommutative rank of linear matrices, related structures and applications  [pdf] 
11:30–12:00  Cole Franks  Analytic algorithms for the moment polytope  [pdf] 
Abstracts
Algorithms for the separation of orbits of matrices (Harm Derksen, University of Michigan)
We consider two group actions on the set of mtuples of n by n matrices, namely the simultaneous conjugation action of GL(n) and the leftright action of SL(n) x SL(n). An invariant can separate two orbits of mtuples if and only if the closures of these orbits are disjoint. In both cases we present a polynomial time algorithm that decides whether the orbit closures of two mtuples intersect. This is joint work with Visu Makam.
Analytic algorithms for the null cone problem (Ankit Garg, Microsoft India)
Null cone is a fundamental object in invariant theory. It is the variety defined by all the homogeneous invariant polynomials for a particular group action. This talk will be focused on the computational complexity of testing membership in the null cone. From a purely algebraic point of view, this problem seems hard, since except in a few cases, one does not have any nice description of the invariant polynomials. However, we will see that there is a good reason to believe that analytic methods can provide provably efficient algorithms for the null cone and we will discuss several examples where this has already been achieved, the most notable being bipartite matching, linear programming, noncommutative rank etc. The analytic approach goes via the KempfNess criterion and connects to the exciting area of geodesically convex optimization.
Noncommutative rank of linear matrices, related structures and applications (Gabor Ivanyos, Hungarian Academy of Sciences)
The noncommutative rank of a matrix with homogeneous linear entries is the rank when we consider the variables as elements of the appropriate free division algebra. This is the same as the maximum size of a square submatrix such that the tuple of coefficient matrices is not in the nullcone of the polynomial invariants for the leftright action of the suitable special linear group. There is a “dual” characterization in terms of large common rectangular zero blocks (after appropriate changes of bases).We will outline a deterministic polynomial time algorithm for computing the noncommutative rank in a twofold constructive way. Firstly, it computes a polynomial invariant for an appropriate submatrix together with a nonvanishing substitution of values from a division algebra of relatively small dimension (actually, even from a matrix algebra) into the variables. Then, in the nonfull rank case, common zero blocks with matching parameters are revealed. We will also discuss related common “echelon forms” for the coefficient matrices and some applications. The algorithm for finding the large zero blocks works along certain flags of subspaces that further “echelonize” the coefficient matrices. These flags are analogous to the alternating forests in algorithms for finding maximum matchings in bipartite graphs. Interestingly, their behavior explain certain special cases when the noncommutative rank coincide with or approximates the usual, “commutative” one (i.e., with the rank when the variables are considered as elements of a commutative field). Some of these special cases will be discussed as well.
The talk is based on joint works with Youming Qiao and K. V. Subrahmanyam.
Analytic algorithms for the moment polytope (Cole Franks, Rutgers University)
Moment polytopes are convex bodies associated to certain group actions on manifolds. When the manifold is a projective variety invariant under the action of a reductive Lie group, it is known that the moment polytope encodes asymptotic information about the irreducible representations of the group occurring in the coordinate ring of the variety. This talk concerns the computational complexity of deciding moment polytope membership. Existing methods include enumerating the (potentially exponentially many) facets and evaluating highest weight polynomials (of potentially exponential degree), but we will discuss analytic algorithms that do not seem to face the same hurdles. These analytic algorithms are also notable for their simplicity and their ability to compute preimages under the moment map, a problem of practical interest. We will discuss how alternating minimization, one of the simplest approaches in optimization, leads to analytic algorithms for Horn’s problem and the quantum marginal problem. Among the conceptual tools in the analysis of these algorithms are “reductions” to the null cone problem and lower bounds for KempfNess functions via representation theory.
Additional Material

Slides and recordings from the Workshop on Optimization, Complexity and Invariant Theory organized by Avi Wigderson at the IAS (June 48, 2018).

Slides from the Tutorial & Workshop on Scaling Algorithms and Applications at FOCS 2019.