The Complexity of Tensor Rank
Marcus Schaefer, Daniel Štefankovič · arXiv (Cornell University) · 2016
We show that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of that field. This implies earlier NP-hardness results by Håstad~\cite{H90}. The hardness proof also implies an algebraic universality result.