Title: Group-theoretic Algorithms for Matrix Multiplication
Speaker: Balazs Szegedy, IAS
Date: January 24, 2006 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We develop fast matrix multiplication algorithms based on the theory of finite group representations, according to the paradigm introduced by Cohn and Umans in 2003. The fastest of these algorithms runs in O(n^2.41) operations. We present two conjectures, either of which (if resolved affirmatively) would imply that the exponent of matrix multiplication is equal to 2.
This is joint work with Henry Cohn, Robert D. Kleinberg, and Christopher Umans, in FOCS 2005. The paper is available on-line at http://theory.csail.mit.edu/~rdk/papers/CKSU05.pdf
A news article about this work is available at http://www.siam.org/pdf/news/174.pdf