Group Theoretic Algorithms For Fast matrix Multiplication

 COMPUTER SCIENCE/DISCRETE MATH II Topic: Group Theoretic Algorithms For Fast matrix Multiplication Speaker: Balazs Szedgedy Affiliation: IAS Date: Tuesday, March 14 Time/Room: 10:30am - 12:30pm/S-101

In 1969 Strassen discovered the surprising fact that it is possible to multiply two 2x2 matrices by using only 7 multiplications. This leads to an algorithm which multiplies two nxn matrices with n^(2.81+o(1)) field operations. Coppersmith and Winograd in 1990 improved the constant 2.81 to 2.376 but the best constant is still unknown. We present group theoretic algorithms for matrix mltiplication and we discuss undelying combinatorial problems. This is a joint work with: H.Cohn, R.Kleinberg and C.Umans