6.890: Matrix Multiplication and Graph Algorithms -- Fall 2021

Time: Tuesdays and Thursdays 11am--12:30pm, 3-270
Instructor: Virginia Vassilevska Williams
Problem Set submission email: 6890mit@gmail.com
Piazza: Sign up here
Office Hours: TBA


This graduate course will explore topics around matrix multiplication (MM) and its use in the design of graph algorithms. We will focus on problems such as transitive closure, shortest paths, graph matching, and many other classical graph problems. Many problems turn out to be equivalent to MM, but we may want to be able to solve them faster anyway. We will explore ways of solving such problems faster, leading to good approximations.

Workload for this course:

Prerequisites: This is an advanced course, meant for graduate students, but it is open to anyone. Good familiarity with algorithmic concepts and good mathematical maturity is necessary. We will try to recall the concepts needed along the way. Having taken courses in algorithms such as 6.046 is particularly useful, otherwise it may be tough to follow the material. There is no textbook for the course, but we will have lecture notes and will catalogue additional reading material as we go.

Announcements: Upcoming topics (the rough plan: subject to change!)