New Results in the Complexity of Matrix Multiplication

Abstract

Determining the complexity of matrix multiplication has been a central problem in complexity theory ever since Strassen showed, in 1969, that one can multiply matrices in O(n2.81) arithmetic operations, strictly better than with the usual algorithm. Bini reduced the problem of the complexity of matrix multiplication to one in multilinear algebra, that of determining the border rank of the matrix multiplication tensor. In this thesis, I prove new border rank bounds, both upper and lower, on certain matrix multiplication tensors as well as on the little Coppersmith-Winograd tensor and its recently introduced skew variant, auxiliary tensors relevant to the study via Strassen’s laser method. Upper bounds are obtained through explicit rank and border rank decompositions. The lower bounds are are obtained principally through representation theory, both of finite and Lie groups. In particular, I present new results for matrix multiplication coming from a recent development in lower bounds due to Buczyńska and Buczyński, the idea of border apolarity.