Explicit lower bounds via geometric complexity theory

Citations Over TimeTop 10% of 2013 papers

Abstract

We prove the lower bound R Mm) ≥ 3/2 m2-2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of Mulmuley and Sohoni's 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 an explicit description of the highest weight vectors in Symd⊗3 (Cn)* in terms of combinatorial objects, called obstruction designs. This description results from analyzing the process of polarization and Schur-Weyl duality.

Related Papers

• → When does cp-rank equal rank?(2013)1 cited
• Some rank equalities of some outer inverses of the same matrix(2009)
• → Generalization of real interval matrices to other fields(2019)