Date & Time:
October 8, 2019 3:30 pm – 4:30 pm
Location:
Ryerson 251, 1100 E. 58th St., Chicago, IL,
10/08/2019 03:30 PM 10/08/2019 04:30 PM America/Chicago Josh Alman (MIT) – Limits on the Universal Method for Matrix Multiplication Department of Mathematics & Computer Science Combinatorics & Theory Seminar Ryerson 251, 1100 E. 58th St., Chicago, IL,

Limits on the Universal Method for Matrix Multiplication

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: Aaron Elmore

Josh Alman

Postdoctoral Researcher, Massachusetts Institute of Technology

I’m a Rabin Postdoc in Theoretical Computer Science at Harvard. I work on algorithm design and complexity theory, and I especially like using algebraic tools to solve problems throughout computer science.

I completed my PhD in Computer Science at MIT, advised by Ryan Williams and Virginia Vassilevska Williams. I spent the first half of grad school at Stanford until I moved to MIT with my advisors.

Before that, I was a Math major at MIT, where I lived on Floorpi in East Campus, and I helped organize the Undergraduate Math Association. I have also interned in the Theory Group at IBM Almaden, worked as a Software Engineer at Addepar, and participated in the REU in Combinatorics at the University of Minnesota, Twin Cities.

Related News & Events

Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube