Document Open Access Logo

Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors

Authors Harm Derksen, Visu Makam, Jeroen Zuiddam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.9.pdf
  • Filesize: 0.74 MB
  • 23 pages

Document Identifiers

Author Details

Harm Derksen
  • Northeastern University, Boston, MA, USA
Visu Makam
  • Radix Trading Europe B.V., Amsterdam, The Netherlands
Jeroen Zuiddam
  • Korteweg-de Vries Institute for Mathematics, University of Amsterdam, The Netherlands

Funding

  • Derksen, Harm: NSF grants IIS-1837985 and DMS-2001460.
  • Makam, Visu: NSF grants CCF-1900460 and the University of Melbourne.
  • Zuiddam, Jeroen: Simons Junior Fellowship and NWO Veni grant VI.Veni.212.284.

Acknowledgements

The authors thank Swastik Kopparty for helpful discussions, and JM Landsberg and Jan Draisma for comments.

Cite AsGet BibTex

Harm Derksen, Visu Makam, and Jeroen Zuiddam. Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CCC.2022.9

Abstract

Since the seminal works of Strassen and Valiant it has been a central theme in algebraic complexity theory to understand the relative complexity of algebraic problems, that is, to understand which algebraic problems (be it bilinear maps like matrix multiplication in Strassen’s work, or the determinant and permanent polynomials in Valiant’s) can be reduced to each other (under the appropriate notion of reduction). In this paper we work in the setting of bilinear maps and with the usual notion of reduction that allows applying linear maps to the inputs and output of a bilinear map in order to compute another bilinear map. As our main result we determine precisely how many independent scalar multiplications can be reduced to a given bilinear map (this number is called the subrank, and extends the concept of matrix diagonalization to tensors), for essentially all (i.e. generic) bilinear maps. Namely, we prove for a generic bilinear map T : V × V → V where dim(V) = n that θ(√n) independent scalar multiplications can be reduced to T. Our result significantly improves on the previous upper bound from the work of Strassen (1991) and Bürgisser (1990) which was n^{2/3 + o(1)}. Our result is very precise and tight up to an additive constant. Our full result is much more general and applies not only to bilinear maps and 3-tensors but also to k-tensors, for which we find that the generic subrank is θ(n^{1/(k-1)}). Moreover, as an application we prove that the subrank is not additive under the direct sum. The subrank plays a central role in several areas of complexity theory (matrix multiplication algorithms, barrier results) and combinatorics (e.g., the cap set problem and sunflower problem). As a consequence of our result we obtain several large separations between the subrank and tensor methods that have received much interest recently, notably the slice rank (Tao, 2016), analytic rank (Gowers-Wolf, 2011; Lovett, 2018; Bhrushundi-Harsha-Hatami-Kopparty-Kumar, 2020), geometric rank (Kopparty-Moshkovitz-Zuiddam, 2020), and G-stable rank (Derksen, 2020). Our proofs of the lower bounds rely on a new technical result about an optimal decomposition of tensor space into structured subspaces, which we think may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • tensors
  • bilinear maps
  • complexity
  • subrank
  • diagonalization
  • generic tensors
  • random tensors
  • reduction
  • slice rank

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 34th Computational Complexity Conference (CCC 2019), pages 12:1-12:24, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.12.
  2. 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.
  3. Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar. On multilinear forms: Bias, correlation, and tensor rank. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), pages 29:1-29:23, 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.29.
  4. Markus Bläser. Fast Matrix Multiplication. Number 5 in Graduate Surveys. Theory of Computing Library, 2013. URL: https://doi.org/10.4086/toc.gs.2013.005.
  5. Markus Bläser. Explicit tensors. In Perspectives in computational complexity, pages 117-130. Springer, 2014. Google Scholar
  6. 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., pages Paper No. 3, 27, 2017. URL: https://doi.org/10.19086/da.1245.
  7. Armand Borel. Linear algebraic groups, volume 126 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1991. URL: https://doi.org/10.1007/978-1-4612-0941-6.
  8. 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.
  9. Peter Bürgisser. Degenerationsordnung und Trägerfunktional bilinearer Abbildungen. PhD thesis, Universität Konstanz, 1990. URL: http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-20311.
  10. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Universal points in the asymptotic spectrum of tensors (extended abstract). In Proceedings of the 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2018), 2018. URL: https://doi.org/10.1145/3188745.3188766.
  11. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Barriers for fast matrix multiplication from irreversibility. In 34th Computational Complexity Conference (CCC 2019), pages 26:1-26:17, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.26.
  12. Alex Cohen and Guy Moshkovitz. Structure vs. randomness for bilinear maps. In 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), 2021. URL: https://doi.org/10.1145/3406325.3451007.
  13. Alex Cohen and Guy Moshkovitz. Partition rank and analytic rank are uniformly equivalent, 2021. URL: http://arxiv.org/abs/2102.10509.
  14. Harm Derksen. The G-stable rank for tensors, 2020. URL: http://arxiv.org/abs/2002.08435.
  15. Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, and Avi Wigderson. Barriers for rank methods in arithmetic complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), pages 1:1-1:19, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.1.
  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. Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, and Avi Wigderson. More barriers for rank methods, via a "numeric to symbolic" transfer. In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 824-844, 2019. URL: https://doi.org/10.1109/FOCS.2019.00054.
  18. Runshi Geng and J. M. Landsberg. On the geometry of geometric rank, 2021. URL: http://arxiv.org/abs/2012.04679.
  19. W. T. Gowers. The slice rank of a direct sum, 2021. URL: http://arxiv.org/abs/2105.08394.
  20. W. T. Gowers and J. Wolf. Linear forms and higher-degree uniformity for functions on 𝐅ⁿ_p. Geom. Funct. Anal., 21(1):36-69, 2011. URL: https://doi.org/10.1007/s00039-010-0106-3.
  21. Ben Joseph Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the gowers norms. Contributions Discret. Math., 4(2), 2009. URL: http://cdm.ucalgary.ca/cdm/index.php/cdm/article/view/133.
  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. Discrete Anal., 2020. URL: http://arxiv.org/abs/1902.11207.
  24. Tali Kaufman and Shachar Lovett. Worst case to average case reductions for polynomials. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 166-175, 2008. URL: https://doi.org/10.1109/FOCS.2008.17.
  25. Pascal Koiran. On tensor rank and commuting matrices, 2020. URL: http://arxiv.org/abs/2006.02374.
  26. Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric rank of tensors and subrank of matrix multiplication. In 35th Computational Complexity Conference (CCC 2020), 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.35.
  27. J. M. Landsberg and Giorgio Ottaviani. Equations for secant varieties of Veronese and other varieties. Ann. Mat. Pura Appl. (4), 192(4):569-606, 2013. URL: https://doi.org/10.1007/s10231-011-0238-6.
  28. Shachar Lovett. The analytic rank of tensors and its applications. Discrete Anal., 2019. URL: https://doi.org/10.19086/da.8654.
  29. Luka Milićević. Polynomial bound for partition rank in terms of analytic rank. Geom. Funct. Anal., 29(5):1503-1530, 2019. URL: https://doi.org/10.1007/s00039-019-00505-4.
  30. Eric Naslund. The partition rank of a tensor and k-right corners in 𝔽_qⁿ. Journal of Combinatorial Theory, Series A, 174:105190, 2020. URL: https://doi.org/10.1016/j.jcta.2019.105190.
  31. Eric Naslund and Will Sawin. Upper bounds for sunflower-free sets. Forum Math. Sigma, 5:Paper No. e15, 10, 2017. URL: https://doi.org/10.1017/fms.2017.12.
  32. Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. Journal of the ACM (JACM), 60(6):1-15, 2013. Google Scholar
  33. Alexander A. Razborov. On submodular complexity measures. In Poceedings of the London Mathematical Society symposium on Boolean function complexity, pages 76-83, 1992. URL: https://dl.acm.org/doi/10.5555/167687.167709.
  34. Robert Robere and Jeroen Zuiddam. Amortized circuit complexity, formal complexity measures, and catalytic algorithms. Electron. Colloquium Comput. Complex., page 35, 2021. URL: https://eccc.weizmann.ac.il/report/2021/035.
  35. Arnold Schönhage. Partial and total matrix multiplication. SIAM J. Comput., 10(3):434-455, 1981. URL: https://doi.org/10.1137/0210032.
  36. Yaroslav Shitov. Counterexamples to Strassen’s direct sum conjecture. Acta Math., 222(2):363-379, 2019. URL: https://doi.org/10.4310/ACTA.2019.v222.n2.a3.
  37. Volker Strassen. Vermeidung von Divisionen. J. Reine Angew. Math., 264:184-202, 1973. Google Scholar
  38. Volker Strassen. Rank and optimal computation of generic tensors. Linear Algebra Appl., 52/53:645-685, 1983. URL: https://doi.org/10.1016/0024-3795(83)80041-X.
  39. 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.
  40. 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.
  41. 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.
  42. Terence Tao. A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound. URL: https://terrytao.wordpress.com, 2016.
  43. Avi Wigderson and Jeroen Zuiddam. Asymptotic spectra: Theory, applications and extensions, 2021. URL: https://staff.fnwi.uva.nl/j.zuiddam/papers/convexity.pdf.
  44. Jeroen Zuiddam. Asymptotic spectra, algebraic complexity and moment polytopes. PhD thesis, University of Amsterdam, 2018. 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 Imprint Privacy Contact