BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Matrix rank is well-known to be multiplicative under the Krone
cker product\, additive under the direct sum\, normalised on identity matri
ces and non-increasing under multiplying from the left and from the right b
y any matrices. In fact\, matrix rank is the only real matrix parameter wit
h these four properties. In 1986 Strassen proposed to study the extension t
o tensors: find all maps from k-tensors to the reals that are multiplicativ
e under the tensor Kronecker product\, additive under the direct sum\, norm
alized on diagonal tensors\, and non-increasing under acting with linear ma
ps on the k tensor factors. Strassen called the collection of these maps th
e "asymptotic spectrum of k-tensors". Strassen proved that understanding th
e asymptotic spectrum implies understanding the asymptotic relations among
tensors\, including the asymptotic rank. In particular\, knowing the asympt
otic spectrum means knowing the arithmetic complexity of matrix multiplicat
ion\, a central problem in algebraic complexity theory. I will give an over
view of known elements in the asymptotic spectrum of tensors\, including ou
r recent construction which is based on information theory and moment polyt
opes. This recent construction is joint work with Matthias Christandl and P
eter Vrana. Then I will introduce the analogous object in graph theory: the
asymptotic spectrum of graphs. I will explain the relation to Shannon capa
city and give an overview of known elements in the asymptotic spectrum of g
raphs.
DTSTAMP:20181105T173500
DTSTART:20180709T141500
CLASS:PUBLIC
LOCATION:Technische Universität Berlin Institut für Mathematik Straße des 1
7. Juni 136 10623 Berlin Room MA 041 (ground floor)
SEQUENCE:0
SUMMARY:Jeroen Zuiddam (CWI\, Amsterdam): Asymptotic spectra of tensors and
graphs: matrix multiplication exponent and Shannon capacity
UID:89792886@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20180709-L-Zuiddam.html
END:VEVENT
END:VCALENDAR