Time+Place: Wednesday 31/12/2014 14:30 Room 337-8 Taub Bld.
Title: Fast matrix multiplication: Limitations of the Coppersmith-Winograd approach
Speaker: Yuval Filmus - CS-Lecture - NOTE UNUSUAL DAY http://www.cs.toronto.edu/~yuvalf/
Affiliation: Institute for Advanced Study in Princeton
Host: Eyal Kushilevitz

Abstract:


How fast can we multiply two nxn matrices?
Strassen (1969) showed how to beat the trivial O(n^3) algorithm: he gave 
an O(n^2.81) algorithm.
Until recently, the fastest known algorithm, due to Coppersmith and 
Winograd (1987), ran in time O(n^2.376).
Recent improvements, extending the work of Coppersmith and Winograd, 
have culminated in an algorithm of Le Gall (2014) running in time 
O(n^2.3729).
We show that this approach cannot yield an algorithm running faster than 
O(n^2.3725).

Coppersmith and Winograd use Strassen's laser method together with an 
identity and its square to obtain their algorithm.
The recent improvements analyze higher powers of the identity, the 32nd 
resulting in Le Gall's algorithm.
We introduces a new framework, the laser method with merging, which can 
be used to analyze all powers of the identity at once.
Using our new framework, we can show that no power of the identity can 
result in an O(n^2.3725) algorithm or better.
Our new framework can potentially lead to even faster algorithms not 
corresponding to powers of the identity.

Joint work with Andris Ambainis (University of Latvia) and Francois Le 
Gall (University of Tokyo).

No familiarity with algebraic complexity theory will be assumed.


Short Bio:

Yuval Filmus studied Computer Science in the Open University of Israel, 
obtained his MSc at the Weizmann Institute, and recently completed his 
PhD at the University of Toronto, advised by Prof. Toni Pitassi.
After spending a semester in the Simons Institute at Berkeley, he is now 
a postdoc at the Institute for Advanced Study in Princeton.
Filmus is interested in several areas of theoretical computer science, 
in combinatorics, and in the interplay between the two, recently 
specializing in analysis of Boolean functions.