Monday, September 15th, 2016 | 4pm-5pm | TBD |

Technion

On the Coppersmith-Winograd approach to matrix multiplication

Ever since Strassen's O(n^{2.81}) matrix multiplication algorithm stunned the mathematical community, the quest for fast matrix multiplication algorithms has been a holy grail in computer science. At first progress was fast, culminating in Coppersmith and Winograd's O(n^{2.376}) algorithm of 1987. Recently interest in the area has reawakened due to work of Stothers, Vassilevska-Williams and Le Gall, who managed to improve the exponent slightly from 2.376 to 2.373. Roughly speaking, Coppersmith and Winograd constructed an edifice turning an "identity" (some kind of mathematical object) into a fast matrix multiplication algorithm. Applying their method on the identity TCW, they obtained an O(n^{2.388}) algorithm. Applying it to TCW^2 (identities can be squared!), they obtained their O(n^{2.376}) algorithm. They stopped there since computing was a lot more cumbersome in the 1980s. Using modern computers, Stothers, Vassilevska-Williams and Le Gall were able to analyze higher powers of TCW (up to TCW^32), and so reduced the exponent to 2.373. Our talk answers the following question: What is the limit of this approach? We show that this approach cannot yield an exponent smaller than 2.372. No prior knowledge will be assumed. Joint work with Andris Ambainis (University of Latvia) and Francois Le Gall (University of Tokyo).