Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR18-086 | 23rd April 2018 14:28

#### Tensor Rank is Hard to Approximate

TR18-086
Authors: Joseph Swernofsky
Publication: 30th April 2018 09:24
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 finite field. We do this via reduction from bounded occurrence 2-SAT.