The complexity of tensor rank

DOI10.1007/s00224-017-9800-yzbMath1396.68061arXiv1612.04338OpenAlexW2560970889MaRDI QIDQ722207

Marcus Schaefer, Daniel Š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) Decidability (number-theoretic aspects) (11U05) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

On the complexity of finding tensor ranks ⋮ Topological art in simple galleries ⋮ Tensor Rank is Hard to Approximate

Cites Work

• Unnamed Item
• Unnamed Item
• Tensor Decompositions and Applications
• Some provably hard crossing number problems
• Global properties of tensor rank
• The computational complexity of some problems of linear algebra
• Intersection graphs of segments
• Mnëv's universality theorem revisited
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Realization spaces of polytopes
• Realizability of Graphs and Linkages
• Tensor rank is NP-complete
• Complexity of Some Geometric and Topological Problems
• Characterizing integers among rational numbers with a universal-existential formula
• On the Complexity of Numerical Analysis
• Bounds for rectilinear crossing numbers
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Most Tensor Problems Are NP-Hard

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