Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Tensor rank is hard to approximate
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
2018 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2018, article id 26Conference paper, Published paper (Refereed)
Abstract [en]

We prove that approximating the rank of a 3-tensor to within a factor of 1+1/1852-δ, for any δ > 0, is NP-hard over any field. We do this via reduction from bounded occurrence 2-SAT.

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2018. article id 26
Series
Leibniz International Proceedings in Informatics, LIPIcs, ISSN 1868-8969 ; 116
Keywords [en]
Approximation Algorithm, Hardness Of Approximation, High Rank Tensor, Slice Elimination, Tensor Rank
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-234497DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.26Scopus ID: 2-s2.0-85052431328ISBN: 9783959770859 (print)OAI: oai:DiVA.org:kth-234497DiVA, id: diva2:1246247
Conference
21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018, University of Princeton, Princeton, United States
Note

QC 20180907

Available from: 2018-09-07 Created: 2018-09-07 Last updated: 2018-09-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Swernofsky, Joseph
By organisation
Theoretical Computer Science, TCS
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 67 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf