Computer Science/Discrete Mathematics Seminar II

Tensors occur throughout mathematics. Their rank, defined in analogy with matrix rank, is however much more poorly understood, both from a structural and algorithmic viewpoints.

This will be an introductory talk to some of the basic issues frustrating us with the understanding of tensor rank. I will define the rank (and border rank) of tensors. I will discuss basic results on the complexity of computing the rank of a given tensor, in the general and some special cases. I will then turn to show the few, weak lower bounds we have for explicit tensors, and discuss new work which explains why better lower bounds cannot be obtained using the best techniques currently available in algebraic geometry and algebraic complexity theory.