[Colloquium] Theory Seminar speaker Josh Alman

[Donna Brooms]

REMINDER: 

Department of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, October 8, 2019
Ryerson 251@ 3:30 pm

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.


Host: Prof. Aaron Potechin





-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20191008/a12bf7d1/attachment.html>