Abstract
Christandl and Zuiddam [Matthias Christandl and Jeroen Zuiddam, 2019] study the multilinear complexity of dfold matrix multiplication in the context of quantum communication complexity. Bshouty [Nader H. Bshouty, 2013] investigates the multilinear complexity of dfold multiplication in commutative algebras to understand the size of socalled 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 dfold multiplication in arbitrary associative algebras. We prove a multilinear generalization of the famous AlderStrassen theorem, which is a lower bound for the bilinear complexity of the (2fold) multiplication in an associative algebra. We show that the multilinear complexity of the dfold multiplication has a lower bound of d ⋅ dim A  (d1)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 dfold multiplication in A: When the semisimple algebra A/rad A is commutative, then the multilinear complexity of the dfold multiplication in A is polynomial in d. On the other hand, when A/rad A is noncommutative, then the multilinear complexity of the dfold 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:112:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772662},
ISSN = {18688969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17664},
URN = {urn:nbn:de:0030drops176645},
doi = {10.4230/LIPIcs.STACS.2023.12},
annote = {Keywords: Multilinear computations, associative algebras, matrix multiplication, AlderStrassen theorem}
}
Keywords: 

Multilinear computations, associative algebras, matrix multiplication, AlderStrassen theorem 
Collection: 

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 
Issue Date: 

2023 
Date of publication: 

03.03.2023 