skip to content

The Challenges of Geometric Complexity Theory

Thursday 17th October 2013 - 10:00 to 11:00
INI Seminar Room 1
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.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons