國立清華大學 數學系

Abstract:
The exponent of matrix multiplication is one of the central open problems in complexity theory. It can be defined using the rank of certain tensors. In this talk, I will introduce the exponent of matrix multiplication and explain its connection to tensor theory. I will discuss the most well-known approach to upper bounding the exponent: the laser method, originally introduced by Strassen in 1987. Several notions of tensor rank have been studied — such as tensor rank, subrank, geometric rank, and others — all of which generalize the usual matrix rank. I will explain how a deeper understanding of these measures contributes to improving upper bounds on the exponent of matrix multiplication via the laser method.