Mulmuley and Sohoni [25, 26] proposed to view the permanent versus determinant problem as a specific orbit closure problem and to attack it by methods from geometric invariant and representation theory. We adopt these ideas towards the goal of showing lower bounds on the border rank of specific tensors, in particular for matrix multiplication. We thus study specific orbit closure problems for the group A key idea from [26] is that the irreducible Gs-representations occurring in the coordinate ring of the G-orbit closure of a stable tensor w ∈ W are exactly those having a nonzero invariant with respect to the stabilizer group of w. However, we prove that by considering Gs-representations, only trivial lower bounds on border rank can be shown. It is thus necessary to study G-representations, which leads to geometric extension problems that are beyond the scope of the subgroup restriction problems emphasized in [25, 26] and its follow up papers. We prove a very modest lower bound on the border rank of matrix multiplication tensors using G-representations. This shows at least that the barrier for Gs-representations can be overcome. To advance, we suggest the coarser approach to replace the semigroup of representations of a tensor by its moment polytope. We prove first results towards determining the moment polytopes of matrix multiplication and unit tensors. * A full version of this paper is available at arxiv.org/abs/1011. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.  Categories and Subject Descriptors Algorithms, Theory Keywords geometric complexity theory, tensor rank, matrix multiplication, orbit closures, multiplicities, Kronecker coefficients We thank Matthias Christandl, Shrawan Kumar, Joseph Landsberg, Laurent Manivel, Ketan Mulmuley, and Jerzy Weyman for helpful discussions. We are grateful to the Fields Institute in Toronto for providing a forum for discussing some questions of GCT in the fall of 2009. Moreover, we thank the Center for Computational Intractability in Princeton for making possible the workshop in Geometric Complexity Theory in 2010, where some of the results presented here were discussed.
The matrix multiplication tensor MM is characterized by its symmetries (e.g., REF ).
Geometric complexity theory and tensor rank
STOC '11
Mathematics Computer Science