Document Open Access Logo

Tensor Rank is Hard to Approximate

Author Joseph Swernofsky

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.26.pdf
  • Filesize: 424 kB
  • 9 pages

Document Identifiers

Author Details

Joseph Swernofsky
  • Kungliga Tekniska Högskolan, Lindstedtsvägen 3, Stockholm SE-100 44, Sweden

Funding

  • Swernofsky, Joseph: Supported by the Knut and Alice Wallenberg Foundation.

Cite As Get BibTex

Joseph Swernofsky. Tensor Rank is Hard to Approximate. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 26:1-26:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.26

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • tensor rank
  • high rank tensor
  • slice elimination
  • approximation algorithm
  • hardness of approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Boris Alexeev, Michael A. Forbes, and Jacob Tsimerman. Tensor rank: Some lower and upper bounds. CoRR, abs/1102.0072, 2011. URL: http://arxiv.org/abs/1102.0072.
  2. Piotr Berman and Marek Karpinski. Efficient amplifiers and bounded degree optimization. Electronic Colloquium on Computational Complexity (ECCC), 8(53), 2001. URL: http://eccc.hpi-web.de/eccc-reports/2001/TR01-053/index.html.
  3. Markus Bläser. On the complexity of the multiplication of matrices of small formats. J. Complexity, 19(1):43-60, 2003. URL: http://dx.doi.org/10.1016/S0885-064X(02)00007-9.
  4. Markus Bläser. Explicit tensors. In Perspectives in Computational Complexity, pages 117-130. Springer, 2014. Google Scholar
  5. Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Generalized matrix completion and algebraic natural proofs. Electronic Colloquium on Computational Complexity (ECCC), 25:64, 2018. URL: https://eccc.weizmann.ac.il/report/2018/064.
  6. Johan Håstad. Tensor rank is np-complete. J. Algorithms, 11(4):644-654, 1990. URL: http://dx.doi.org/10.1016/0196-6774(90)90014-6.
  7. Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. SIAM Review, 51(3):455-500, 2009. URL: http://dx.doi.org/10.1137/07070111X.
  8. Joseph B Kruskal. Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear algebra and its applications, 18(2):95-138, 1977. Google Scholar
  9. Julian D Laderman. A noncommutative algorithm for multiplying 3× 3 matrices using 23 multiplications. Bulletin of the American Mathematical Society, 82(1):126-128, 1976. Google Scholar
  10. J. M. Landsberg and Mateusz Michalek. Abelian tensors. CoRR, abs/1504.03732, 2015. URL: http://arxiv.org/abs/1504.03732.
  11. Viñtor Yakovlevich Pan. Methods of computing values of polynomials. Russian Mathematical Surveys, 21(1):105-136, 1966. Google Scholar
  12. Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. Electronic Colloquium on Computational Complexity (ECCC), 17:2, 2010. URL: http://eccc.hpi-web.de/report/2010/002.
  13. Marcus Schaefer and Daniel Stefankovic. The complexity of tensor rank. CoRR, abs/1612.04338, 2016. URL: http://arxiv.org/abs/1612.04338.
  14. Yaroslav Shitov. How hard is the tensor rank? arXiv preprint arXiv:1611.01559, 2016. Google Scholar
  15. Amir Shpilka. Lower bounds for matrix product. CoRR, cs.CC/0201001, 2002. URL: http://arxiv.org/abs/cs.CC/0201001.
  16. Zhao Song, David P. Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. CoRR, abs/1704.08246, 2017. URL: http://arxiv.org/abs/1704.08246.
  17. Volker Strassen. Gaussian elimination is not optimal. Numerische mathematik, 13(4):354-356, 1969. Google Scholar
  18. Nengkun Yu, Eric Chitambar, Cheng Guo, and Runyao Duan. Tensor rank of the tripartite state |w⟩^⊗ n. Physical Review A, 81(1):014301, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact