## Matrix multiplication

Yuval Filmus

An exposition on algorithms for matrix multiplication, in two parts:

- Part 1:
- The arithmetic model.
- Bilinear normal form for matrix multiplication.
- Tensor notation and tensor rank.
- Border rank.
- Schönhage’s $\tau$ theorem (the asymptotic sum inequality).
- Coppersmith’s $\tilde{O}(n^2)$ algorithm for multiplying rectangular matrices.

- Part 2:
- The laser method.
- The Coppersmith–Winograd algorithms.
- Capacity: the fundamental combinatorial underpinning of the Coppersmith–Winograd method.

These talks were given in the Toronto Student Seminar on 2/2/2012 and 9/2/2012, though the second one has been significantly updated since.

The talks were given again in the IAS theory seminar, on 25/2/2014 and 4/3/2014. The second part has been significantly updated: the combinatorial construction has been simplified following Davie and Stothers, and the general presentation follows Le Gall’s recent paper.