The complexity of tensor rank

DOI10.1007/S00224-017-9800-YMaRDI QIDQ722207zbMATHOpenAlexFDO

Authors Marcus Schaefer, D. Štefankovič

Publication date 23 July 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.04338

zbMATH Keywords

computational complexitytensor rankexistential theory of fields

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decidability of theories and sets of sentences (03B25) Decidability (number-theoretic aspects) (11U05)

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{aa}stad~cite{H90}. The hardness proof also implies an algebraic universality result.

Recommendations

• On the complexity of finding tensor ranks
• Tensor rank is NP-complete
• Tensor rank is hard to approximate
• scientific article; zbMATH DE number 7387190
• Bounds on the tensor rank
• Geometric complexity theory and tensor rank
• An upper bound for the tensor rank
• Tensor decompositions and rank increment conjecture
• Tensor decompositions in rank \(+1\)
• Rank properties and computational methods for orthogonal tensor decompositions

Cites work

• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• Bounds for rectilinear crossing numbers
• Characterizing integers among rational numbers with a universal-existential formula
• Complexity of some geometric and topological problems
• Global properties of tensor rank
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Intersection graphs of segments
• Mnëv's universality theorem revisited
• Most tensor problems are NP-hard
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Complexity of Numerical Analysis
• Realizability of graphs and linkages
• Realization spaces of polytopes
• Some provably hard crossing number problems
• Tensor Decompositions and Applications
• Tensor rank is NP-complete
• The computational complexity of some problems of linear algebra

Cited in

(24)

• Several remarks on tensor rank computation
• Length Complexity of Tensor Products
• Rank of a tensor and quantum entanglement
• Typical tensorial rank
• On the tensor rank of the \(3 \times 3\) permanent and determinant
• Most tensor problems are NP-hard
• On the average condition number of tensor rank decompositions
• Barriers for rank methods in arithmetic complexity
• scientific article; zbMATH DE number 7561763 (Why is no real title available?)
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Topological art in simple galleries
• Solving the tensor isomorphism problem for special orbits with low rank points: cryptanalysis and repair of an Asiacrypt 2023 commitment scheme
• Tensor codes for the rank metric
• On the complexity of finding tensor ranks
• Hankel Tensor Decompositions and Ranks
• Tensor rank is NP-complete
• Non-interactive commitment from non-transitive group actions
• Notions of tensor rank
• Tensor rank is hard to approximate
• The complexity of tensor circuit evaluation
• Monomial isomorphism for tensors and applications to code equivalence problems
• On classifying continuous constraint satisfaction problems
• scientific article; zbMATH DE number 7387190 (Why is no real title available?)
• The complexity of recognizing geometric hypergraphs

This page was built for publication: The complexity of tensor rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722207)