2017/06/13 by Friedman, Joel
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1706.04225
We develop a notion of \em inner rank as a tool for obtaining lower bounds on the rank of matrix multiplication tensors. We use it to give a short proof that the border rank (and therefore rank) of the tensor associated with n× n matrix multiplication over an arbitrary field is at least 2n2-n+1. While inner rank does not provide improvements to currently known lower bounds, we argue that this notion merits further study.