<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><span style="background-color: rgba(255, 255, 255, 0);">Departments of Mathematics & Computer Science<br>Combinatorics & Theory Seminar<br><br><a href="x-apple-data-detectors://0" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="0" style="text-decoration-color: rgba(0, 0, 0, 0.258824);">Tuesday, </a>October 8<br>Ry 251 <a href="x-apple-data-detectors://1" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="1" style="text-decoration-color: rgba(0, 0, 0, 0.258824);">@3:30pm</a><br><br>Josh Alman <br>MIT <br><br>Title: </span><span style="font-weight: bold; background-color: rgba(255, 255, 255, 0);">Limits on the Universal Method for Matrix Multiplication</span><span style="background-color: rgba(255, 255, 255, 0);"><br><br>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-Win<wbr>ograd 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. </span><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);"> No background knowledge about matrix multiplication algorithms is assumed. </span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Some of the talk is based on joint work with Virginia Vassilevska Williams. </span></div><div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);"> Refreshments will be served prior to the talk at 3:15 pm Ry 255. </span><div dir="ltr"></div></div></div></body></html>