A Caltech Library Service

A Group-theoretic Approach to Fast Matrix Multiplication

Cohn, Henry and Umans, Christopher (2003) A Group-theoretic Approach to Fast Matrix Multiplication. In: 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE , Los Alamitos, CA, pp. 438-449. ISBN 0-7695-2040-5

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 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+o(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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2003 IEEE. Date of Current Version: 20 October 2003. We are grateful to Michael Aschbacher, Noam Elkies, Bobby Kleinberg, Lászlό Lovász, Amin Shokrollahi, David Vogan, and Avi Wigderson for helpful discussions.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number7847069
Record Number:CaltechAUTHORS:20111026-095124253
Persistent URL:
Official Citation:Cohn, H.; Umans, C.; , "A group-theoretic approach to fast matrix multiplication," Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on , vol., no., pp. 438- 449, 11-14 Oct. 2003 doi: 10.1109/SFCS.2003.1238217 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27435
Deposited By: Ruth Sustaita
Deposited On:26 Oct 2011 17:21
Last Modified:26 Oct 2011 17:21

Repository Staff Only: item control page