License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.12
URN: urn:nbn:de:0030-drops-176645
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17664/
Bläser, Markus ;
Mayer, Hendrik ;
Shringi, Devansh
On the Multilinear Complexity of Associative Algebras
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.
BibTeX - Entry
@InProceedings{blaser_et_al:LIPIcs.STACS.2023.12,
author = {Bl\"{a}ser, Markus and Mayer, Hendrik and Shringi, Devansh},
title = {{On the Multilinear Complexity of Associative Algebras}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {12:1--12:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17664},
URN = {urn:nbn:de:0030-drops-176645},
doi = {10.4230/LIPIcs.STACS.2023.12},
annote = {Keywords: Multilinear computations, associative algebras, matrix multiplication, Alder-Strassen theorem}
}
|
Keywords: |
|
Multilinear computations, associative algebras, matrix multiplication, Alder-Strassen theorem |
|
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
03.03.2023 |
