Computer Science/Discrete Mathematics Reading Seminar

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 of tensors (and a few asymptotic variants). 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 barrier results explaining why better lower bounds cannot be obtained using the best techniques currently available in algebraic geometry and algebraic complexity theory.