The Complexity of Tensor Rank

2016/12/13 by Marcus Schaefer, Schaefer, Marcus, Daniel Štefankovič +1 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.48550/arxiv.1612.04338

openalex publication_date 2016/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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~\citeH90. The hardness proof also implies an algebraic universality result.

Cited by

• Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

Related

• On the complexity of finding tensor ranks
• How hard is the tensor rank?
• More barriers for rank methods, via a "numeric to symbolic" transfer
• Tensor Rank and Complexity
• Notions of Tensor Rank