Abstract

It is a remarkable fact that two prominent problems of algebraic complexity theory, the permanent versus determinant problem and the tensor rank problem, can be restated as explicit orbit closure problems. This offers the potential for proving lower complexity bounds by relying on methods from algebraic geometry and representation theory. This basic idea for the tensor rank problem goes back to work by Volker Strassen from the mid eighties. It leads to challenging problems regarding the irreducible representions of symmetric groups over the complex numbers (tensor products and plethysms).

In the first part of the talk, we will present the general framework, explain some negative results, and state some open problems. Then we will move on to outline some recent progress for proving lower bounds on the border rank of the matrix multiplication tensor. This is achieved by the explicit construction of highest weight vectors vanishing on the (higher secant) varieties of tensors of border rank at most r.