Document Open Access Logo

On the Multilinear Complexity of Associative Algebras

Authors Markus Bläser, Hendrik Mayer, Devansh Shringi

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.12.pdf
  • Filesize: 0.76 MB
  • 18 pages

Document Identifiers

Author Details

Markus Bläser
  • Universität des Saarlandes, Saarland Informatics Campus, Saarbrücken, Germany
Hendrik Mayer
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Devansh Shringi
  • University of Toronto, Canada

Acknowledgements

Hendrik Mayer would like to thank the MIT MISTI-Germany program for funding his internship.

Cite As Get BibTex

Markus Bläser, Hendrik Mayer, and Devansh Shringi. On the Multilinear Complexity of Associative Algebras. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.STACS.2023.12

Abstract

Christandl and Zuiddam [Matthias Christandl and Jeroen Zuiddam, 2019] study the multilinear complexity of d-fold matrix multiplication in the context of quantum communication complexity. Bshouty [Nader H. Bshouty, 2013] investigates the multilinear complexity of d-fold multiplication in commutative algebras to understand the size of so-called testers. The study of bilinear complexity is a classical topic in algebraic complexity theory, starting with the work by Strassen. However, there has been no systematic study of the multilinear complexity of multilinear maps.
In the present work, we systematically investigate the multilinear complexity of d-fold multiplication in arbitrary associative algebras. We prove a multilinear generalization of the famous Alder-Strassen theorem, which is a lower bound for the bilinear complexity of the (2-fold) multiplication in an associative algebra. We show that the multilinear complexity of the d-fold multiplication has a lower bound of d ⋅ dim A - (d-1)t, where t is the number of maximal twosided ideals in A. This is optimal in the sense that there are algebras for which this lower bound is tight. Furthermore, we prove the following dichotomy that the quotient algebra A/rad A determines the complexity of the d-fold multiplication in A: When the semisimple algebra A/rad A is commutative, then the multilinear complexity of the d-fold multiplication in A is polynomial in d. On the other hand, when A/rad A is noncommutative, then the multilinear complexity of the d-fold multiplication in A is exponential in d.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Mathematics of computing
Keywords
  • Multilinear computations
  • associative algebras
  • matrix multiplication
  • Alder-Strassen theorem

Metrics

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

References

  1. A. Alder and V. Strassen. On the algorithmic complexity of associative algebras. Theoret. Comput. Sci., 15:201-211, 1981. Google Scholar
  2. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 522-539. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  3. Markus Bläser. Lower bounds for the bilinear complexity of associative algebras. Comput. Complexity, 9:73-112, 2000. Google Scholar
  4. Markus Bläser. A complete characterization of the algebras of minimal bilinear complexity. SIAM J. Comput., 34(2):277-298, 2004. URL: https://doi.org/10.1137/S0097539703438277.
  5. Markus Bläser. Fast matrix multiplication. Theory Comput., 5:1-60, 2013. URL: https://doi.org/10.4086/toc.gs.2013.005.
  6. Markus Bläser and Bekhan Chokaev. Algebras of minimal multiplicative complexity. In Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012, pages 224-234. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/CCC.2012.13.
  7. Markus Bläser and Christian Ikenmeyer. Introduction to geometric complexity theory. Lecture notes, 2018. URL: https://pcwww.liv.ac.uk/~iken/teaching_sb/summer17/introtogct/gct.pdf.
  8. Nader H. Bshouty. Multilinear complexity is equivalent to optimal tester size. Electron. Colloquium Comput. Complex., page 11, 2013. URL: https://eccc.weizmann.ac.il/report/2013/011, URL: https://arxiv.org/abs/TR13-011.
  9. Nader H. Bshouty. Testers and their applications. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 327-352. ACM, 2014. URL: https://doi.org/10.1145/2554797.2554828.
  10. Harry Buhrman, Matthias Christandl, and Jeroen Zuiddam. Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 24:1-24:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.24.
  11. Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic Complexity Theory. Springer, 1997. Google Scholar
  12. Matthias Christandl and Jeroen Zuiddam. Tensor surgery and tensor rank. Comput. Complex., 28(1):27-56, 2019. URL: https://doi.org/10.1007/s00037-018-0164-8.
  13. P. M. Cohn. Algebra, volume 3. Wiley, 1991. Google Scholar
  14. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progression. J. Symbolic Computation, 9:251-280, 1990. Google Scholar
  15. Yurij A. Drozd and Vladimir V. Kirichenko. Finite Dimensional Algebras. Springer, 1994. Google Scholar
  16. François Le Gall. Powers of tensors and fast matrix multiplication. In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  17. J. M. Landsberg. New lower bounds for the rank of matrix multiplication. SIAM J. Comput., 43(1):144-149, 2014. URL: https://doi.org/10.1137/120880276.
  18. J. M. Landsberg. Geometry and Complexity Theory. Cambridge University Press, 2017. Google Scholar
  19. Noam Nisan and Avi Wigderson. Lower bounds for arithmetic circuits via partial derivatives (preliminary version). In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 16-25. IEEE Computer Society, 1995. URL: https://doi.org/10.1109/SFCS.1995.492458.
  20. Richard S. Pierce. Associative Algebras. Springer, 1982. Google Scholar
  21. Ramprasad Saptharishi et al. A selection of lower bounds in arithmetic circuit complexity. Version 2021-07-27. URL: https://github.com/dasarpmar/lowerbounds-survey/releases/tag/v9.0.3.
  22. Andrew J. Stothers. On the complexity of matrix multiplication. PhD thesis, The University of Edinburgh, 2010. Google Scholar
  23. Volker Strassen. Gaussian elimination is not optimal. Num. Math., 13:354-356, 1969. Google Scholar
  24. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proc. 44th Ann. ACM Symp. on Theory of Computing, pages 887-898, 2012. Google Scholar
  25. Shmuel Winograd. On multiplication of 2 × 2-matrices. Lin. Alg. Appl., 4:381-388, 1971. 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