====== Henry Cohn (Microsoft Research) ======

====== Representation Theory, Combinatorics, and Fast Matrix Multiplication ======

===== Abstract for the Colloquium and Combinatorics Seminar 2006 May 4 =====

How quickly can one multiply two large matrices? Surprisingly, this natural question has never been completely answered. In 1969 Volker Strassen showed how to multiply n-by-n matrices in roughly n<sup>2.81</sup> operations, which was an amazing improvement over the obvious n<sup>3</sup> algorithm; currently the best method known (discovered by Coppersmith and Winograd in 1986) reaches exponent 2.376. Chris Umans and I proposed using representation theory of finite groups to develop fast algorithms. Together with Bobby Kleinberg and Balazs Szegedy we found a simpler proof of the Coppersmith-Winograd theorem, and formulated several combinatorial conjectures that if true would yield asymptotically optimal algorithms. The talk will cover background, discuss what we can achieve, and outline how one might hope to go further.


----