Mathematisches Kolloquium

Title: Irreversibility of tensors of minimal border rank and barriers for fast matrix multiplication
Speaker: Prof. Dr. Markus Blaeser
Abstract:
Determining the asymptotic complexity of matrix multiplication is a central problem in
algebraic complexity theory. The best upper bounds on the so-called exponent of matrix
multiplication ω are obtained by starting with an 'efficient' tensor, taking a high power
of it and degenerating a matrix multiplication out of it. In the first part of the talk, we
give a gentle introduction to the design of fast matrix multiplication algorithms.

In the recent years, several so-called barrier results have been established. A barrier result
shows a lower bound on the best upper bound on ω that can be obtained by a certain
restriction starting with a certain tensor. We prove the following barrier over the complex
numbers: Starting with a tensor of minimal border rank satisfying a certain genericity
condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary
restrictions. This is astonishing since the tensors of minimal border rank look like the
most natural candidates for designing fast matrix multiplication algorithms. We prove
this by showing that all these tensors are irreversible, using a structural characterization
of these tensors.

Der Gast wird von Prof. Dr. Moritz Weber betreut.
Alle Interessenten sind zum Vortrag herzlich eingeladen.