[Theory] UC Theory Seminar: a reminder

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, October 8
Ry 251 @3:30pm

Josh Alman 
MIT 

Title: Limits on the Universal Method for Matrix Multiplication

Abstract: We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a generalization based on restrictions of powers of tensors which subsumes these two approaches, which we call the Universal method. We then prove concrete lower bounds on the algorithms one can design by applying the Universal method to many different tensors. Our proofs use new tools for upper bounding the asymptotic slice rank of a wide range of tensors. Our main result is that the Universal method applied to any Coppersmith-Winograd tensor (the family of tensors used in all record-holding algorithms from the past 30+ years) cannot yield a bound on omega, the exponent of matrix multiplication, better than 2.16805. 

 No background knowledge about matrix multiplication algorithms is assumed. 
Some of the talk is based on joint work with Virginia Vassilevska Williams. 

 Refreshments will be served prior to the talk at 3:15 pm Ry 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20191007/59dada84/attachment.html>