Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science (Q2672320)

The paper contains a survey on recent developments on the theoretical complexity of matrix multiplication. A matrix multiplication algorithm, fundamental process in most mathematical theories, can be encoded in a three-way tensor, and consequently analyzed with multilinear algebra tools. In particular, the complexity of an algorithm can be rephrased in terms of the rank of the corresponding tensor. The author illustrates the history and the state of the art of the study of the rank of the multiplication tensors. Emphasis is given to the geometric approach, related to the properties of secant varieties of some Segre variety. The structure of secant varieties leads in a natural way to the notion of border rank of a tensor, which in practice is the minimal rank that can be obtained with a small local deformation. Advances in the computation of the border rank, due to the application of representation theory and to some recent results on the deformation theory of homogeneous ideals and on non-saturated limit ideals, are described in the paper. The author considers in particular the case of \(3\times 3\) matrices, for which the precise values of the rank and the border rank of the matrix multiplication tensor are still unknown. In the general case of \(n\times n\) matrix, there is a long-standing conjecture that the rank should grow as \(n^2\), when \(n\) goes to infinity. Recent results and new tools toward the proof of the conjecture, with their limits and their possible developments, are described and discussed.