The complexity of tensor rank
From MaRDI portal
Publication:722207
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
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
