Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR18-086 | 3rd July 2018 20:00

#### Tensor Rank is Hard to Approximate

Revision #1
Authors: Joseph Swernofsky
Accepted on: 3rd July 2018 20:00
Keywords:

Abstract:

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.

Changes to previous version:

Follow review suggestions. Cite Bläser et al. 2018.

### 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.