An introduction to the Asymptotic Spectra of Preordered Semirings

Abstract: In algebraic complexity theory, a flagship problem is to determine the exponent of matrix multiplication, that is, the infimum of real numbers $\omega$ such that $n \times n$ matrix multiplication can be computed using $n^{\omega+o(1)}$ arithmetic operations. Motivated by this problem, Strassen developed the theory of asymptotic spectra, initially focusing on the preordered semiring of tensors. In this talk, we give an introduction to the theory of asymptotic spectra. We first define preordered semirings and their asymptotic spectra. We then discuss Strassen's duality theorem, which characterizes the asymptotic preorder on a semiring in terms of elements in its asymptotic spectrum. Finally, we discuss the broad applicability of the theory, its generalizations, and related research problems.

computational complexityrings and algebras

Audience: learners

Tropical mathematics and machine learning

Series comments: Tropical mathematics, machine learning, category theory and anything tech+math are welcome.