Explicit Lower Bounds via Geometric Complexity Theory

Understand

We prove the lower bound R(M_m) \geq 3/2 m^2 - 2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of the geometric complexity theory (GCT) program.

• 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 the new combinatorial concept of obstruction designs, which encode highest weight vectors in Sym^d\otimes^3(C^n)^* and provide new insights into Kronecker coefficients.