The complexity of tensor rank

DOI10.1007/S00224-017-9800-YzbMATH Open1396.68061arXiv1612.04338OpenAlexW2560970889MaRDI QIDQ722207FDOQ722207

Authors: Marcus Schaefer, D. Štefankovič 

Publication date: 23 July 2018

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

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.

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

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

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)

Cites Work

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

Cited In (21)

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

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)