Name
Abstract | ||
|---|---|---|
We develop a new, group-theoretic approach to bounding the exponent of matrix multiplication. There are two components to this approach: (1) identifying groups G that admit a certain type of embedding of matrix multiplication into the group algebra \mathbb{C}[G] and (2) controlling the dimensions of the irreducible representations of such groups. We present machinery and examples to support (1), including a proof that certain families of groups of order n^{2 + 0(1)} support n 脳 n matrix multiplication, a necessary condition for the approach to yield exponent 2. Although we cannot yet completely achieve both (1) and (2), we hope that it may be possible, and we suggest potential routes to that result using the constructions in this paper. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/SFCS.2003.1238217 | FOCS |
Keywords | Field | DocType |
fast matrix multiplication,order n,group-theoretic approach,matrix multiplication,group algebra,certain family,groups g,irreducible representation,certain type,support n,n matrix multiplication,computational complexity,group theory | Discrete mathematics,Combinatorics,Algebra,Invertible matrix,Associative algebra,Matrix ring,Diagonal matrix,Centrosymmetric matrix,Mathematics,Binary operation,DFT matrix,Matrix group | Conference |
ISSN | ISBN | Citations |
Proceedings of the 44th Annual Symposium on Foundations of
Computer Science, 11-14 October 2003, Cambridge, MA, IEEE Computer Society,
pp. 438-449 | 0-7695-2040-5 | 44 |
PageRank | References | Authors |
4.79 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henry Cohn | 1 | 192 | 20.23 |
| Christopher Umans | 2 | 879 | 55.36 |