BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Determining the asymptotic algebraic complexity of matrix mult
iplication is a central problem in algebraic complexity theory. The best up
per bounds on the so-called exponent of matrix multiplication if obtained b
y starting with an "efficient" tensor\, taking a high power and degeneratin
g a matrix multiplication out of it. In the recent years\, several so-cal
led barrier results have been established. A barrier result shows a lower b
ound on the best upper bound for the exponent of matrix multiplication that
can be obtained by a certain restriction starting with a certain tensor. W
e prove the following barrier over the complex numbers: Starting with a ten
sor of minimal border rank satisfying a certain genericity condition\, exce
pt for the diagonal tensor\, it is impossible to prove ω = 2 using arbitrar
y restrictions. This is astonishing since the tensors of minimal border ran
k look like the most natural candidates for designing fast matrix multiplic
ation algorithms. We prove this by showing that all of these tensors are ir
reversible\, using a structural characterisation of these tensors. Joi
nt work with Vladimir Lysikov.
DTSTAMP:20200922T143600
DTSTART:20201102T141500
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Markus Bläser (Universität Saarbrücken): Irreversibility of tensors
of minimal border rank and barriers for fast matrix multiplication
UID:106853215@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20201102-L-Blaeser.html
END:VEVENT
END:VCALENDAR