AG 1, AG 2, AG 3, AG 4, AG 5   Info

AG Audience

English

30 Minutes

Saarbrücken

Matrix Multiplication (MM) is the one of the fundamental algorithmic problems in algebra. It is also known to be computationaly equivalent to several others (e.g. determinant, solving systems of linear equations, matrix inversion, computing LUP decompositions). Since Strassen's startling discovery of a O(n^2.81) algorithm for MM in 1969, several algorithms have been proposed, the best one so far is the algorithm of Coppersmith and Winograd (1987) with complexity O(n^2.38). Since 1987 no progress has been made until last year, when H. Cohn and C. Uhmans developed a completely new group-theoretic framework for performing MM. At this year's FOCS they (and others) show that it can actually be used to multiply matrices as fast as Coppersmith-Winograd's algorithm (but not in the same way!). They also pose a very simple (in statement) and purely combinatorial conjecture which if true would give an almost quadratic algorithm for MM.

I am going to show how the new approach works without giving to many details, and also present the combinatorial conjecture.

Marcin Mucha

--email hidden

passcode not visible

logged in users only