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 |

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.