Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
is there a connection between the inherent complexity of binary/integer multiplication algorithms and matrix multiplication algorithms? if so what is a ref that outlines/discusses it?
some related history: Schonhage/Strassen give a fast algorithm for binary multiplication and Strassen also gave a faster matrix multiplication method.
Here is a relevant reference and Sasho has graciously added a high-level summary.
A Group-theoretic Approach to Fast Matrix Multiplication by Cohn and Umans. (2004, arxiv).
There is a close analogy between the framework we propose in this paper and the well-known algorithm for multiplying two degree n polynomials in O(n log n) operations using the Fast Fourier Transform (FFT). In this section we elucidate this analogy to give a high-level description of our technique.
On a very high level, the FFT-base polynomial multiplication algorithm can be seen as the following strategy: 1) embed the polynomials as elements of the group algebra of a not-too-large abelian group; 2) apply the DFT to the group algebra elements in order to embed them as complex-valued diagonal matrices; 3) multiply the diagonal matrices.
(Note: the group algebra here is the algebra of formal "linear combinations" of group elements with complex or real coefficients).
The same approach almost works for matrix multiplication. Step 1) becomes hard, where it was trivial with polynomials. The embedding can be done with abelian groups of size $n^3$, and no better, so for $n^{2 + o(1)}$ size groups you need to abandon commutativity. Then 2) turns out to still be doable with non-abelian groups using the appropriate generalization of DFT that you get from representation theory, but the resulting object is a block-diagonal matrix rather than a diagonal matrix. Then 3) is no longer the trivial pointwise multiplication operation, but multiplication of smaller matrices. Bounding the sizes of these matrices is a question about dimensions of irreducible representations of the group we used.
See also the follow-up Group-Theoretic Algorithms for Matrix Multiplication by Cohn, R. Kleinberg, Szegedy, and Umans (2005, arxiv).
Perhaps there have been advancements (or even a survey) since then. Of course this probably doesn't answer your question about how the complexities of the problems are related....
