FoCM 2014 conference

Workshop A6 - Real Number Complexity

December 12, 17:00 ~ 17:30 - Room C11

Geometric Complexity Theory, Tensor Rank, and Representation Theory

Christian Ikenmeyer

Texas A&M University, USA   -

Mulmuley and Sohoni conjectured that the permanent vs determinant problem can be resolved using explicit so-called representation theoretic occurence obstructions. It is still unknown whether these objects exist or not, even for small examples. We show that in the simpler (but still highly interesting) setting of matrix multiplication these obstructions indeed exist! We prove the lower bound $R(M_m) \geq \frac 3 2 m^2 − 2$ on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic occurence obstructions. While this bound is weaker than the one recently obtained by Landsberg and Ottaviani, these are the first significant lower bounds obtained within the GCT program. Behind the proof is basically Schur-Weyl duality and an explicit description of highest weight vectors in terms of combinatorial objects.

Joint work with Peter Bürgisser (Technische Universität Berlin, Germany).

View abstract PDF