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.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20201102-L-Bla
 eser.html
END:VEVENT
END:VCALENDAR