2026-07-23T07:03:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9430 2024-03-06T10:44:22Z ddc:004 open_access

Tensor Rank is Hard to Approximate Swernofsky, Joseph tensor rank high rank tensor slice elimination approximation algorithm hardness of approximation We prove that approximating the rank of a 3-tensor to within a factor of 1 + 1/1852 - delta, for any delta > 0, is NP-hard over any field. We do this via reduction from bounded occurrence 2-SAT. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joseph Swernofsky 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.26 urn:nbn:de:0030-drops-94309 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.26 eng https://creativecommons.org/licenses/by/3.0/legalcode