# Fast matrix multiplication

 Computer Science/Discrete Mathematics Seminar II Topic: Fast matrix multiplication Speaker: Yuval Filmus Affiliation: Member, School of Mathematics Date: Tuesday, March 4 Time/Room: 10:30am - 12:30pm/S-101 Video Link: https://video.ias.edu/csdm/2014/0304-YuvalFilmus

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that $O(n^{2.81})$ operations suffice. We survey the classical theory of fast matrix multiplication, starting with Strassen's algorithm and culminating with the state-of-the-art Coppersmith-Winograd algorithm and its recent improvements. We also describe Coppersmith's $O(n^2 log^2 n)$ algorithm for multiplying rectangular matrices, used by Ryan Williams in his separation of ACC and NEXP.