2012/10/31 by Peter Bürgisser, Christian Ikenmeyer, Bürgisser, Peter +1
Computer Science · Engineering · #14L24 #20C30 #68Q17 #Advanced Graph Theory Research #Computational Complexity (cs.CC) #F.1.3 #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Representation Theory (math.RT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1210.8368
openalex publication_date 2012/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 Symd⊗3(Cn)^* and provide new insights into Kronecker coefficients.