Date: Tuesday, March 14, 2006
Title: Representation Theory and Fast Matrix Multiplication
Abstract: 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 nbyn matrices in roughly n2.81 operations, which was an amazing improvement over the obvious n3 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 CoppersmithWinograd theorem, and formulated several 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.
Speaker: Henry Cohn
Institution: Microsoft
