You are here

Efficient algorithms for moment polytopes and the null cone problem from invariant theory

Peter Bürgisser
TU Berlin
Monday, October 28, 2019 - 14:00
Suppose a reductive group G acts linearly on a finite dimensional complex vector space V. The corresponding null cone, which may be thought of the set of "singular objects'', consists of those vectors that cannot be distinguished from the zero vector by means of polynomial invariants. The null cone was introduced by Hilbert in his seminal work on invariant theory around 1900.
Quite surprisingly, the computational problem of testing membership to the null cone turned out to be of relevance for geometric complexity theory, quantum information theory, and other areas. Notably, a thorough study of the null cone for the simultaneous left/right action on tuples of matrices was crucial for finding a deterministic polynomial time algorithm for verifying algebraic identities.

Despite the algebraic nature of the problem, numerical optimization algorithms seem to be the mostefficient general methods for solving the null cone problem. This also applies to the related problem of testing membership to momentpolytopes, which e.g., generalizes Horn's problem on the eigenvalues of sums of matrices. 

The long term goal is to find polynomial time algorithms for these problems.
In the special case of abelian groups, such algorithms are provided by linear programming, e.g., by interior methods. Condition numbers are likely to play an important role in this endeavour.

Sign in