Barriers for Scaling Algorithms in Invariant Theory

In recent years, Computational Invariant Theory has seen significant progress in optimization techniques: so-called scaling algorithms approximately minimize the norm along an orbit under a group action. Such algorithms also give rise to methods for /deciding /null-cone membership, i.e. whether zero is in a given orbit closure. Both computational problems have versatile applications in mathematics, physics, statistics and computer science. However, only for certain group actions polynomial time algorithms are known.

In this talk, we give a short introduction to these computational problems and provide exponential bounds on certain complexity parameters. These results explain why current techniques are, in general, only known to run in exponential time and strongly motivate the search for new scaling algorithms.

This is joint work with Cole Franks, see arXiv:2102.06652, arxiv.org/abs/2102.06652.