<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class=""><b class="">Department of Mathematics & Computer Science</b></div><div class=""><b class="">Combinatorics & Theory Seminar</b></div><div class=""><b class=""><br class=""></b></div><div class=""><b class="">Tuesday, October 8, 2019</b></div><div class=""><b class="">Ryerson 251@ 3:30 pm</b></div><div class=""><br class=""></div><div class=""><b class="">Josh Alman</b></div><div class=""><b class="">MIT</b></div><div class=""><br class=""></div><div class=""><div style="font-family: LucidaGrande;" class="">Title: Limits on the Universal Method for Matrix Multiplication</div><div style="font-family: LucidaGrande;" class=""><br class=""></div><div style="font-family: LucidaGrande;" class="">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.<br class=""></div><div style="font-family: LucidaGrande;" class=""><br class=""></div><div style="font-family: LucidaGrande;" class="">No background knowledge about matrix multiplication algorithms is assumed. Some of the talk is based on joint work with Virginia Vassilevska Williams.</div><div class=""><div style="font-family: Helvetica; font-size: inherit; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; widows: 2; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; text-align: -webkit-auto; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; text-align: -webkit-auto; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; text-align: -webkit-auto;" class=""><div style="font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; text-align: -webkit-auto; font-size: 11px;" class=""><br class="webkit-block-placeholder"></div><div style="font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; text-align: -webkit-auto;" class="">Host: Prof. Aaron Potechin</div></div></div></div></div></div></div><div class=""><div style="font-size: inherit; text-align: -webkit-auto; font-family: Helvetica; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; orphans: 2; widows: 2; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; text-align: -webkit-auto; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; text-align: -webkit-auto; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; text-align: -webkit-auto;" class=""></div></div></div></div></div><div class="">
<div style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; font-size: 11px;"></p><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class=""><p class="MsoNormal" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;"><br class=""></p></div></div></div></div></div></div></div></body></html>