The Basic Notions Seminar

Organized by William Stein

Mondays 3-4pm in Science Center 507 at Harvard University

List of Talks Last Year's Seminar

On the complexity of matrix multiplication

Joseph Landsberg

October 25, 2004

How many multiplications are necessary to multiply two $n\times n$ matrices? Using standard row-column technique, one performs $n^3$ multiplications. In 1965, Hugo vonStrassen presented an explicit algorithm to multiply $2\times 2$ matrices using seven multiplications. By breaking matrices up into blocks, this enabled a reduction of exponent for the $n\times n$ case. Today, after much work, the asymptotic exponent has been reduced from $3$ to approximately $2.376$. Finding the best exponent is a central, if not the central, open problem in algebraic complexity theory.

There is considerable geometry related to this problem. I will explain how elementary algebraic geometry (secant varieties of Segre varieties), representation theory (Schur-Weyl correspondence), projective differential geometry (osculating spaces of curves!) and exterior differential systems (prolongation) come into play; and how I recently proved that Strassen's result for $2\times 2$ matrices is the best possible, solving a problem that had been open for $39$ years. Along the way I'll also explain applications to questions in algebraic statistics.

This talk will be acessible to anyone who can multiply matrices.