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. https://resolver.caltech.edu/CaltechAUTHORS:20111026-095124253
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20111026-095124253
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 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: |
| |||||||||
| 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: |
| |||||||||
| DOI: | 10.1109/SFCS.2003.1238217 | |||||||||
| Record Number: | CaltechAUTHORS:20111026-095124253 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20111026-095124253 | |||||||||
| 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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1238217&isnumber=27770 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 27435 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Ruth Sustaita | |||||||||
| Deposited On: | 26 Oct 2011 17:21 | |||||||||
| Last Modified: | 09 Nov 2021 16:48 |
Repository Staff Only: item control page
