On the Multilinear Complexity of Associative Algebras

Markus Bläser, Hendrik Mayer, Devansh ShringiSTACS 2023 · OpenReview

TL;DR

This paper tackles the problem of understanding the "multilinear complexity" of multiplying elements in associative algebras, a generalization of matrix multiplication. The authors provide a new lower bound for this complexity and reveal a crucial dichotomy: the complexity is polynomial in the number of multiplications if the "semisimple part" of the algebra is commutative, but exponential otherwise. This work is significant for its systematic study of a previously underexplored area with implications for quantum communication and algorithm design.

What Problem Does This Paper Address?

The paper investigates the "multilinear complexity" of multiplying $d$ elements in an associative algebra $A$. This is a generalization of the well-studied problem of bilinear complexity (e.g., matrix multiplication, where $d=2$). While bilinear complexity has been extensively studied, the multilinear case for $d > 2$ has not been systematically explored. Understanding this complexity is important for theoretical computer science, with connections to quantum communication complexity and the design of efficient algorithms for tasks like identity testing. The core challenge is to find general bounds and understand how the algebraic structure of $A$ influences this complexity.

Methods

The authors generalize the classic Alder-Strassen theorem, which provides a lower bound for bilinear complexity. Their key contributions include:

  • Multilinear Alder-Strassen Theorem: They establish a lower bound for the multilinear complexity of $d$-fold multiplication in an associative algebra $A$ as $d \cdot \dim A - (d-1)t$, where $t$ is the number of maximal two-sided ideals in $A$. This bound is shown to be tight for certain algebras.
  • Radical Removal: A crucial technique is showing that the multilinear complexity of an algebra $A$ is closely related to the complexity of its quotient algebra $A/\text{rad}(A)$, where $\text{rad}(A)$ is the radical of the algebra. This simplifies the problem by allowing them to focus on semisimple algebras.
  • Dichotomy: The paper proves a fundamental dichotomy based on the structure of $A/\text{rad}(A)$:
  • If $A/\text{rad}(A)$ is commutative, the multilinear complexity is polynomial in $d$.
  • If $A/\text{rad}(A)$ is noncommutative, the multilinear complexity is exponential in $d$.
  • Flattening Technique: For specific cases like matrix algebras, they employ the "flattening" technique, which transforms a multilinear tensor into a matrix whose rank provides a lower bound on the tensor's rank and thus the multilinear complexity.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The structure of $A/\text{rad}(A)$ dictates complexity: The most striking insight is the dichotomy between commutative and noncommutative semisimple parts. This suggests that the "core" structure of an algebra (after removing nilpotent elements) is the primary determinant of how complex its higher-order multiplications are.
  • Generalization of Alder-Strassen is tight: The new lower bound is not just theoretical; it's shown to be achievable, meaning there are algebras where the complexity precisely matches this bound. This provides a strong benchmark for understanding multilinear complexity.
  • Radical is "removable" for complexity analysis: The ability to relate the complexity of $A$ to $A/\text{rad}(A)$ is a powerful simplification. It means that the "nilpotent part" of an algebra, while important for other algebraic properties, doesn't fundamentally change the growth rate of the multilinear complexity with respect to $d$.

Key Results

  • Lower Bound: For an associative algebra $A$ with $t$ maximal two-sided ideals, the $d$-fold multiplication complexity $R(A, d)$ satisfies $R(A, d) \geq d \cdot \dim A - (d-1)t$.
  • Polynomial vs. Exponential Growth:
    • If $A/\text{rad}(A)$ is commutative, $R(A, d)$ is polynomial in $d$. For example, for commutative algebras, it's bounded by $d^{(s-1)(D+1)} \cdot D^{(D+3)s}$, where $s$ is the nilpotency index of the radical and $D$ is the dimension.
  • If $A/\text{rad}(A)$ is noncommutative, $R(A, d)$ is exponential in $d$. This is demonstrated for matrix algebras $M_n(D)$ where $n > 1$, yielding a lower bound of $l \cdot n^{d+1}$ (for odd $d$, where $l = \dim D$).

Limitations and Future Work

  • Field Dependence: Some results hold for "perfect fields" (e.g., characteristic zero, finite fields, algebraically closed fields). The behavior over non-perfect fields might differ.
  • Upper Bounds: While lower bounds are established, achieving tight upper bounds for all cases, especially for the polynomial growth scenario, remains an active area. The paper provides specific upper bounds for commutative algebras and upper triangular matrices, but a general tight upper bound for the polynomial case is complex.
  • Practical Algorithms: The paper notes that multilinear computations are not directly practical for evaluating $d$-fold products due to the lack of result reuse (unlike standard algorithms). The theoretical bounds are crucial for understanding fundamental complexity limits rather than designing immediate algorithms.
  • Future Work: The authors suggest exploring more refined techniques to improve upper bounds, particularly for the polynomial growth case, and investigating the implications of their findings for specific applications like quantum communication complexity and tester design. The structure of the radical and its interaction with the semisimple part is highlighted as a key area for further study.

Summary updated

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
@inproceedings{blaser2023multilinear,
  author = {Markus Bläser and Hendrik Mayer and Devansh Shringi},
  title = {{On the Multilinear Complexity of Associative Algebras}},
  booktitle = {STACS},
  year = {2023},
  url = {https://openreview.net/forum?id=2unhsoeSlE},
}

Loading related content...

Figure