Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Tensor Rank is Hard to Approximate

RSS-Feed




Revision #1
Authors: Joseph Swernofsky
Accepted on: 3rd July 2018 20:00
Downloads: 59
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
Downloads: 457
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 finite field. We do this via reduction from bounded occurrence 2-SAT.



ISSN 1433-8092 | Imprint