Asymptotic Spectra and Applications
In 1969, Strassen shocked the computational world with his subcubic algorithm for multiplying matrices. Attempting to understand the best possible algorithm for this problem, Strassen went on to develop his magnificent theory of asymptotic spectra in three papers between 1987--1991. Expressed in the great generality of partially ordered semirings, the centerpiece of this theory is a duality theorem between the asymptotic "rank" of elements, and a topological space which is called asymptotic spectrum. This duality theorem is a vast generalization of linear programming duality (in which we have a semigroup rather than a semiring), and indeed also of certain versions of the Positivstellensatz, the duality theorem of polynomial inequalities over the Reals. Focusing on understanding the structure of the asymptotic spectrum of matrix multiplication, the theory has provided surprising connectivity and convexity theorems for it.
Strassen's theory has led to many subsequent results, especially new algorithmic, structural and barrier results on matrix multiplication, and more generally for the semiring of tensors (which includes the matrix multiplication tensors). Perhaps even more impressively, the generality of Strassen's theory has been applied recently to the study of a variety of very different settings and parameters, in diverse fields including communication theory, graph theory, probability theory, quantum information theory and computational complexity.
This lecture gives an elementary introduction to Strassen's theory of asymptotic spectra, and serves as an invitation to find more applications of the theory. I will not assume any specific background knowledge for the lecture.
Science Park 904, room C0.110 and online.