### DIMACS Theoretical Computer Science Seminar

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