Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-086 | 23rd April 2018 14:28

Tensor Rank is Hard to Approximate

RSS-Feed




TR18-086
Authors: Joseph Swernofsky
Publication: 30th April 2018 09:24
Downloads: 160
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