Asymptotic spectra and their applications I
These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.
Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalized on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties.
In 1986 Strassen proposed to study the extension to tensors: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalized on diagonal tensors, and non-increasing under acting with linear maps on the k tensor factors. Strassen called the collection of these maps the "asymptotic spectrum of k-tensors". Strassen proved that understanding the asymptotic spectrum implies understanding the asymptotic relations among tensors, including the asymptotic rank. More precisely, the asymptotic spectrum gives a dual characterization of asymptotic rank. In particular, knowing the asymptotic spectrum implies knowing the algebraic complexity of matrix multiplication, a central problem in algebraic complexity theory.
A recent new instantiation of the abstract theory of asymptotic spectra is the "asymptotic spectrum of graphs". Analogous to the situation for tensors, understanding the asymptotic spectrum of graphs implies understanding the Shannon capacity, a graph parameter capturing the zero-error communication capacity of noisy communication channels. More precisely, the asymptotic spectrum gives a dual characterization of Shannon capacity.
In the first talk, I begin with discussing three applications: the matrix multiplication exponent, asymptotic induced matchings in k-partite k-uniform hypergraphs, and the Shannon capacity of graphs. Then we will discuss the asymptotic spectrum of tensors and the asymptotic spectrum of graphs, and the relation to the three applications. Finally, we will see the asymptotic spectrum of an abstract semiring with a Strassen preorder and Strassen's spectral theorem.
In the second talk, I plan to sketch the proof of Strassen's spectral theorem for an abstract semiring with a Strassen preorder. Then I will give an overview of known elements in the asymptotic spectrum of tensors, including our recent construction which is based on information theory and moment polytopes. This recent construction is joint work with Matthias Christandl and Peter Vrana. Then we will see an overview of known elements in the asymptotic spectrum of graphs. Finally, we will discuss the Coppersmith-Winograd method for getting lower bounds on the asymptotic induced matching number.
I do not assume the audience to have any special knowledge.
Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalized on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties.
In 1986 Strassen proposed to study the extension to tensors: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalized on diagonal tensors, and non-increasing under acting with linear maps on the k tensor factors. Strassen called the collection of these maps the "asymptotic spectrum of k-tensors". Strassen proved that understanding the asymptotic spectrum implies understanding the asymptotic relations among tensors, including the asymptotic rank. More precisely, the asymptotic spectrum gives a dual characterization of asymptotic rank. In particular, knowing the asymptotic spectrum implies knowing the algebraic complexity of matrix multiplication, a central problem in algebraic complexity theory.
A recent new instantiation of the abstract theory of asymptotic spectra is the "asymptotic spectrum of graphs". Analogous to the situation for tensors, understanding the asymptotic spectrum of graphs implies understanding the Shannon capacity, a graph parameter capturing the zero-error communication capacity of noisy communication channels. More precisely, the asymptotic spectrum gives a dual characterization of Shannon capacity.
In the first talk, I begin with discussing three applications: the matrix multiplication exponent, asymptotic induced matchings in k-partite k-uniform hypergraphs, and the Shannon capacity of graphs. Then we will discuss the asymptotic spectrum of tensors and the asymptotic spectrum of graphs, and the relation to the three applications. Finally, we will see the asymptotic spectrum of an abstract semiring with a Strassen preorder and Strassen's spectral theorem.
In the second talk, I plan to sketch the proof of Strassen's spectral theorem for an abstract semiring with a Strassen preorder. Then I will give an overview of known elements in the asymptotic spectrum of tensors, including our recent construction which is based on information theory and moment polytopes. This recent construction is joint work with Matthias Christandl and Peter Vrana. Then we will see an overview of known elements in the asymptotic spectrum of graphs. Finally, we will discuss the Coppersmith-Winograd method for getting lower bounds on the asymptotic induced matching number.
I do not assume the audience to have any special knowledge.
Date
Affiliation
Member, School of Mathematics