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