Computer Science/Discrete Mathematics Seminar II

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