Cole Franks, Rutgers University

Abstract

In many cases, a group action on a manifold can be associated with a map 
called a moment map. Surprisingly, the image of the manifold under this 
map is always a convex polytope, known as its moment polytope. Moment 
polytope membership can often be expressed as an optimization problem 
which is convex only in the Abelian case. Whether moment polytope 
membership can be decided in polynomial time is a fundamental open 
problem with deep consequences in algebraic complexity theory and 
elsewhere.

I'll discuss an approach to moment polytope membership through 
optimization. For example, in a recent joint work we obtain an extremely 
simple algorithm for tensor scaling, i.e. approximately scaling tensors 
to arbitrary prescribed marginals (whenever possible). Improving the 
run-time of our tensor scaling algorithm to polylog(eps) would result 
in a polynomial time algorithm for moment polytope membership in this 
special case, and would have applications in polynomial identity 
testing, computing Brascamp-Lieb constants, and optimization problems 
related to tensor rank, to name a few. If time permits I will discuss a 
geodesically convex optimization algorithm that works in a much more 
general setting.

Joint work with with Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, 
and Avi Wigderson