Tensor Rank is Hard to Approximate

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.26OpenAlexW2805640305MaRDI QIDQ5009520

Joseph Swernofsky

Publication date: 4 August 2021

Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.26

zbMATH Keywords

approximation algorithmhardness of approximationtensor rankhigh rank tensorslice elimination

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

The tensor rank of semifields of order 16 and 81

Cites Work

• Tensor Decompositions and Applications
• The complexity of tensor rank
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• On the complexity of the multiplication of matrices of small formats
• Abelian tensors
• Gaussian elimination is not optimal
• On the max-min and tropical CP-rank conjectures
• Explicit Tensors
• Tensor-rank and lower bounds for arithmetic formulas
• Tensor rank is NP-complete
• A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
• Low rank approximation with entrywise l ₁ -norm error
• Generalized matrix completion and algebraic natural proofs

This page was built for publication: Tensor Rank is Hard to Approximate