Fall 2014

Geometric Complexity Theory and Tensor Rank

Wednesday, September 17th, 2014 4:40 pm5:20 pm

Add to Calendar


Calvin Lab Auditorium

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) >= 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.