[Facets-of-complexity] Invitation and link to Monday Lecture - November 2nd 2020 - online via zoom

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture.
All Monday Lectures and Colloquia of winter term 20/21 will be held online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on November 2nd 2020 at 14:15 h.

Online via:
Zoom - Invitation

Time: Monday, November 2nd - 14:15 h

Lecture: Markus Bläser (Universität Saarbrücken)

Title: Irreversibility of tensors of minimal border rank and barriers for fast matrix multiplication

Abstract:

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.