SCS Recruiting Seminar: Josh Alman

Event Details
  • Date/Time:
    • Tuesday February 2, 2021 - Wednesday February 3, 2021
      11:00 am - 11:59 am
  • Location: BlueJeans
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

Tess Malone, Communications Officer

tess.malone@cc.gatech.edu

Summaries

Summary Sentence: Algorithms and Barriers for Fast Matrix Multiplication

Full Summary: No summary paragraph submitted.

Media
  • Josh Alman Josh Alman
    (image/png)

TITLE: Algorithms and Barriers for Fast Matrix Multiplication

ABSTRACT:

Matrix multiplication is one of the most basic algebraic operations. Since Strassen’s surprising breakthrough algorithm from 1969, which showed that matrices can be multiplied faster than the most straightforward algorithm, algorithmic problems from nearly every area of computer science have been sped up by clever reductions to matrix multiplication. It is popularly conjectured that two n × n matrices can be multiplied in roughly O(n^2) time, but we don’t yet have the algorithmic techniques needed to achieve this.

In this talk, I’ll give an overview of my work on this important problem in the broad context of my research on algorithm design and complexity theory for algebraic problems. First, I’ll give an overview of known applications of matrix multiplication, including some new applications to nearest neighbor search and processing data streams. Second, I’ll talk about the fastest known algorithm for matrix multiplication, which runs in time O(n^2.37286), which I recently designed with Virginia Vassilevska Williams. Third, I’ll describe new barrier results which help to explain why we’ve been stuck for so long on this problem, and describe what kinds of insights are needed for further improvements.

BIO:

Josh Alman is a Michael O. Rabin postdoctoral fellow in theoretical computer science at Harvard University. He earned his Ph.D. in computer science from MIT in 2019, where he was advised by Virginia Vassilevska Williams and Ryan Williams. He works on both algorithm design and complexity theory, and much of his work combines tools and insights from both areas. He’s particularly interested in developing algebraic tools like algorithms for matrix multiplication and Fourier transforms, and applying them to problems throughout computer science. His awards include the European Association of TCS Distinguished Dissertation Award, the George M. Sprowls Award for outstanding Ph.D. theses in computer science at MIT, and best student paper awards at CCC 2019 and FOCS 2019.

WATCH HERE: https://bluejeans.com/493104294

Additional Information

In Campus Calendar
No
Groups

College of Computing, School of Computer Science

Invited Audience
Faculty/Staff, Postdoc, Public, Graduate students, Undergraduate students
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Tess Malone
  • Workflow Status: Published
  • Created On: Jan 26, 2021 - 4:10pm
  • Last Updated: Jan 27, 2021 - 7:02pm