Prof. Mateusz Michałek (University of Konstanz)

In our lectures we will show how algebra and geometry interacts with computations. We will introduce k-linear maps – a generalization of linear maps – also known as tensors. We will see that tensors correspond to well known operations, like matrix multiplication. Our main focus will be on relating the computational complexity of the given operations with algebraic properties of tensors.

Just as linear maps correspond to (2 dimensional) matrices, k-linear maps correspond to higher dimensional boxes filled with numbers. We will provide generalizations of the notion of rank. As we will see, for tensors, there are several possible generalizations. And finding rank of a tensor is much, much harder than finding rank of a matrix! However, once the correct language is developed we will see that tensors can help us find new, unexpected algorithms. Such an algorithm will be encoded as a special (algebraic) presentation of a tensor. In some cases, we will be even able to prove the existence of an algorithm of a given complexity, without being able to provide the algorithm explicitly.

Finally, we will see how geometry comes into play. Tensors, corresponding to computational problems, will form vector spaces. Inside these vector spaces, there will be varieties – geometric shapes – corresponding to problems of low complexity. Thus, deciding on the complexity of a given problem will be reduced to deciding if a given point belongs to a fixed variety.