ECCC-Report TR18-086https://eccc.weizmann.ac.il/report/2018/086Comments and Revisions published for TR18-086en-usTue, 03 Jul 2018 20:00:58 +0300
Revision 1
| Tensor Rank is Hard to Approximate |
Joseph Swernofsky
https://eccc.weizmann.ac.il/report/2018/086#revision1We 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.Tue, 03 Jul 2018 20:00:58 +0300https://eccc.weizmann.ac.il/report/2018/086#revision1
Paper TR18-086
| Tensor Rank is Hard to Approximate |
Joseph Swernofsky
https://eccc.weizmann.ac.il/report/2018/086We 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.Mon, 30 Apr 2018 09:24:39 +0300https://eccc.weizmann.ac.il/report/2018/086