The Complexity of Tensor Rank

Abstract

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.

fixed error in Section 3.3

Cited by in corpus (2)

• Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
• Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits