Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Tensors in Computer Science

Prof. Dr. Markus Bläser

Prof. Dr. Frank-Olaf Schreyer

Time & Date

If a matrix is a square filled with numbers, then a higher-order tensor is an n-dimensional cube filled with numbers. Recent years have seen a dramatic rise of interest by computer scientists in the mathematics of higher-order tensors. The notion of matrix rank can be generalized to higher-order tensors. While matrix rank can be efficiently computed by, say, Gaussian eliminination, computing the rank of a tensor of order 3 is NP-hard. The question of the complexity of matrix multiplication can be formulated as the question of the rank of a certain tensor. We will mainly focus on applications in complexity theory and quantum computation. In particular, it is very unlikely that we will deal with applications in machine learning.



Oral exams in the semester break