Group-Theoretic Algorithms for Matrix Multiplication
Speaker: Bobby Kleinberg , UC Berkeley and Cornell
Date: November 22 2005
Time: 4:15PM to 5:30PM
Location: G449 Patil/Kiva
Host: Ronitt Rubinfeld, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: http://theory.csail.mit.edu/toc-seminars/2005/We present a group-theoretic approach to producing fast algorithms for
matrix multiplication. In this framework, one devises algorithms by
constructing non-abelian groups with certain properties. The
algorithms themselves are natural and are based on taking the discrete
Fourier transform over these groups.
We construct several families of groups that achieve matrix
multiplication exponent significantly less than 3 (but not better than
the current best bound, 2.376...). This leads to two appealing
conjectures, one combinatorial and the other algebraic. Either one
would imply that the exponent of matrix multiplication is 2.
This is joint work with Henry Cohn, Balazs Szegedy, and Chris Umans.
See other events that are part of Theory Colloquium Fall 2005
See other events happening in November 2005
