Document Open Access Logo

Geometric Rank of Tensors and Subrank of Matrix Multiplication

Authors Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.35.pdf
  • Filesize: 0.56 MB
  • 21 pages

Document Identifiers

Author Details

Swastik Kopparty
  • Rutgers University, Piscataway, NJ, USA
Guy Moshkovitz
  • Institute for Advanced Study, Princeton, NJ, USA
  • DIMACS, Rutgers University, Piscataway, NJ, USA
Jeroen Zuiddam
  • Institute for Advanced Study, Princeton, NJ, USA

Funding

  • Kopparty, Swastik: Research supported in part by NSF grants CCF-1253886, CCF-1540634, CCF-1814409 and CCF-1412958, and BSF grant 2014359. Some of this research was done while visiting the Institute for Advanced Study.
  • Moshkovitz, Guy: This work was conducted at the Institute for Advanced Study, enabled through support from the National Science Foundation under grant number CCF-1412958, and at DIMACS, enabled through support from the National Science Foundation under grant number CCF-1445755.
  • Zuiddam, Jeroen: Research supported by the National Science Foundation under Grant Number DMS-1638352.

Acknowledgements

We would like to thank Avi Wigderson for helpful conversations.

Cite AsGet BibTex

Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric Rank of Tensors and Subrank of Matrix Multiplication. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 35:1-35:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.35

Abstract

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the subrank of tensors and the independence number of hypergraphs. We prove that the geometric rank is smaller than the slice rank of Tao, and relate geometric rank to the analytic rank of Gowers and Wolf in an asymptotic fashion. As a first application, we use geometric rank to prove a tight upper bound on the (border) subrank of the matrix multiplication tensors, matching Strassen’s well-known lower bound from 1987.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Theory of computation
Keywords
  • Algebraic complexity theory
  • Extremal combinatorics
  • Tensors
  • Bias
  • Analytic rank
  • Algebraic geometry
  • Matrix multiplication

Metrics

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

Related Versions

References

  1. Josh Alman. Limits on the universal method for matrix multiplication. In Proceedings of the 34th Computational Complexity Conference (CCC 2019), pages 12:1-12:24, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.12.
  2. Josh Alman and Virginia Vassilevska Williams. Limits on all known (and some unknown) approaches to matrix multiplication. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018), pages 580-591, 2018. URL: https://doi.org/10.1109/FOCS.2018.00061.
  3. Andris Ambainis, Yuval Filmus, and François Le Gall. Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract). In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pages 585-593, 2015. URL: https://doi.org/10.1145/2746539.2746554.
  4. Daniel Berend and Yuri Bilu. Polynomials with roots modulo every integer. Proc. Amer. Math. Soc., 124(6):1663-1671, 1996. URL: https://doi.org/10.1090/S0002-9939-96-03210-8.
  5. Abhishek Bhowmick and Shachar Lovett. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory, 2015. URL: http://arxiv.org/abs/1506.02047.
  6. Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar. On multilinear forms: Bias, correlation, and tensor rank. arXiv, 2018. URL: http://arxiv.org/abs/1804.09124.
  7. Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans. On cap sets and the group-theoretic approach to matrix multiplication. Discrete Anal., 2017. URL: https://doi.org/10.19086/da.1245.
  8. Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A Grochow, and Chris Umans. Which groups are amenable to proving exponent two for matrix multiplication? arXiv, 2017. URL: http://arxiv.org/abs/1712.02302.
  9. Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, and Frank-Olaf Schreyer. Variety membership testing, algebraic natural proofs, and geometric complexity theory, 2019. URL: http://arxiv.org/abs/1911.02534.
  10. Jop Briët. Subspaces of tensors with high analytic rank. arXiv, 2019. URL: http://arxiv.org/abs/1908.04169.
  11. Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren Math. Wiss. Springer-Verlag, Berlin, 1997. URL: https://doi.org/10.1007/978-3-662-03338-8.
  12. Matthias Christandl, Angelo Lucia, Péter Vrana, and Albert H. Werner. Tensor network representations from the geometry of entangled states, 2018. URL: http://arxiv.org/abs/1809.08185.
  13. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Universal points in the asymptotic spectrum of tensors (extended abstract). In Proceedings of 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC’18). ACM, 2018. URL: https://doi.org/10.1145/3188745.3188766.
  14. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Barriers for Fast Matrix Multiplication from Irreversibility. In Amir Shpilka, editor, 34th Computational Complexity Conference (CCC 2019), volume 137, pages 26:1-26:17, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.26.
  15. Zeev Dvir, János Kollár, and Shachar Lovett. Variety evasive sets. Comput. Complexity, 23(4):509-529, 2014. URL: https://doi.org/10.1007/s00037-013-0073-9.
  16. Jordan S. Ellenberg and Dion Gijswijt. On large subsets of 𝔽ⁿ_q with no three-term arithmetic progression. Ann. of Math. (2), 185(1):339-343, 2017. URL: https://doi.org/10.4007/annals.2017.185.1.8.
  17. Yuval Filmus, Konstantin Golubev, and Noam Lifshitz. High dimensional hoffman bound and applications in extremal combinatorics, 2019. URL: http://arxiv.org/abs/1911.02297.
  18. Michael D. Fried and Moshe Jarden. Field arithmetic, volume 11 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics. Springer-Verlag, Berlin, second edition, 2005. Google Scholar
  19. W. T. Gowers and J. Wolf. Linear forms and higher-degree uniformity for functions on Fⁿ_p. Geom. Funct. Anal., 21(1):36-69, 2011. URL: https://doi.org/10.1007/s00039-010-0106-3.
  20. Daniel R. Grayson and Michael E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at URL: http://www.math.uiuc.edu/Macaulay2/.
  21. Joe Harris. Algebraic geometry: a first course, volume 133. Springer Science &Business Media, 1992. Google Scholar
  22. Oliver Janzer. Low analytic rank implies low partition rank for tensors, 2018. URL: http://arxiv.org/abs/1809.10931.
  23. Oliver Janzer. Polynomial bound for the partition rank vs the analytic rank of tensors. arXiv, 2019. URL: http://arxiv.org/abs/1902.11207.
  24. P. Koiran. Randomized and deterministic algorithms for the dimension of algebraic varieties. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 36-45, October 1997. URL: https://doi.org/10.1109/SFCS.1997.646091.
  25. Serge Lang and André Weil. Number of points of varieties in finite fields. Amer. J. Math., 76:819-827, 1954. URL: https://doi.org/10.2307/2372655.
  26. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pages 296-303, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  27. Shachar Lovett. The analytic rank of tensors and its applications. Discrete Analysis, 2019. URL: https://doi.org/10.19086/da.
  28. Luka Milićević. Polynomial bound for partition rank in terms of analytic rank. Geometric and Functional Analysis, 29(5):1503-1530, 2019. URL: https://doi.org/10.1007/s00039-019-00505-4.
  29. Eric Naslund and Will Sawin. Upper bounds for sunflower-free sets. In Forum of Mathematics, Sigma, volume 5. Cambridge University Press, 2017. Google Scholar
  30. Sage. SageMath, the Sage Mathematics Software System (Version 8.1), 2017. URL: https://www.sagemath.org.
  31. Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987. URL: https://doi.org/10.1515/crll.1987.375-376.406.
  32. Volker Strassen. The asymptotic spectrum of tensors. J. Reine Angew. Math., 384:102-152, 1988. URL: https://doi.org/10.1515/crll.1988.384.102.
  33. Volker Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 413:127-180, 1991. URL: https://doi.org/10.1515/crll.1991.413.127.
  34. Terence Tao. A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, 2016. URL: https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound.
  35. B. L. van der Waerden. Algebra. Vol. I. Springer-Verlag, New York, 1991. URL: https://doi.org/10.1007/978-1-4612-4420-2.
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 Imprint Privacy Contact