SEARCH Events
Event Title: OR
Speaker Last Name:    OR
Year: (yyyy)


Mathematics Colloquium

EVENT DETAIL

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 n-by-n matrices in roughly n-2.81 operations, which was an amazing improvement over the obvious n-3 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 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

 

Back to current Colloquium List
Back to UM Math seminars page

   

Department of Mathematics   |   2074 East Hall   |  530 Church Street  
Ann Arbor, MI 48109-1043
Phone: 734.764-0335   |   Fax: 734.763-0937

The page last modified
Site errors should be directed to math-webmaster@umich.edu