Group-theoretic algorithms for matrix multiplication

I will present the main ideas behind two recent papers that propose a new, group-theoretic approach for matrix multiplication. The approach was first introduced in "A Group-theoretic Approach to Fast Matrix Multiplication" by H. Cohn and C. Umans in 2003. In "Group-theoretic algorithms for matrix multiplication" (2005), H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans develop the approach further and obtain algorithms that are asymptotically faster than the standard, cubic algorithm. In the talk, I will summarize the necessary algebra and representation theory, illustrate the group-theoretic approach on the simpler problem of multiplying polynomials using the Fast Fourier Transform, and discuss one of the "sub-cubic" algorithms developed in the second paper. I will end the talk with some conjectures, proposed in the second paper, that would imply a quadratic matrix multiplication algorithm.