Springe direkt zu Inhalt

Lecture by Markus Bläser (Universität Saarbrücken): Irreversibility of tensors of minimal border rank and barriers for fast matrix multiplication

Nov 02, 2020 | 02:15 PM

Determining the asymptotic algebraic complexity of matrix multiplication is a central problem in algebraic complexity theory. The best upper bounds on the so-called exponent of matrix multiplication if obtained by starting with an "efficient" tensor, taking a high power and degenerating a matrix multiplication out of it. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication 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 of these tensors are irreversible, using a structural characterisation of these tensors.

Joint work with Vladimir Lysikov.

Time & Location

Nov 02, 2020 | 02:15 PM


Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)