[DMO] Nils Van de Berg: Using slice rank for lower bounds on fast matrix multiplication

08 March 2023 14:00 till 15:00 - Location: EEMCS Lecture Hall H, LH.01.340 | Add to my calendar

The exponent of matrix multiplication is an open problem in theoretical computer science. Since the initial development by Strassen it has been known that the complexity of multiplying two n by n matrices is somewhere between O(n^2) and O(n^3). Advances on the upper bound have brought the exponent down to 2.372. It is widely conjectured that the complexity is O(n^2) and indeed no better lower bounds have been found. However development of upper bounds has focussed on certain methods and it is possible to find lower bounds on these methods. In 2019 Alman showed that a general type of method could not obtain a better bound than 2.168. For this he used the slice rank, a notion defined by Tao based on work by Ellenberg and Gijswijt. For my master thesis I have studied his paper and the slice rank. I wish to present the ideas in this paper and some of my small own advancements.