## 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
Office Hours: TBA

Description:

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.

• In-class presentation on a research paper related to the course, or on your own research. In addition, a 1 page summary of the ideas you found most interesting (if you read a paper) or of the outcomes of your research project (if you did one).
• [OPTIONAL]: We plan to have weekly open problem sessions: might be virtual, TBA . These are optional, but if you want to try to do research on the topics of this course, this is a great opportunity!

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:
• 9/16: Lecture notes for lecture 3 are here
• 9/14: Problem set 1 is out: here
• 9/14: Lecture notes for lecture 2 are here
• 9/9: Lecture notes for lecture 1 are here
• 8/25: Look here for fun stuff to happen!

Upcoming topics (the rough plan: subject to change!)
• 9/9: Introduction to matrix multiplication. Equivalences with other linear algebraic operations. Boolean matrix multiplication (BMM) and triangles.
• 9/14: Combinatorial algorithms for BMM: Four-Russians alg. and more [HW1 out]
• 9/16: Seidel's algorithm for APSP.
• 9/21: Zwick's algorithm for APSP and Hitting set arguments.
• 9/23: Yuster/Zwick's Distance oracle and application
• 9/28: All pairs earliest arrivals, bottleneck paths and the dominance product [HW1 due, HW2 out]
• 9/30: Successor and witness matrices; computing actual paths
• 10/5: Minimum Weight Triangles, Equivalences between APSP and other problems (e.g. graph radius)
• 10/7: Distance product for structured matrices: bounded differences
• 10/12: Girth in unweighted graphs; algorithms for even cycles; HW2 due
• 10/14: Approximation algorithms for the girth; HW3 out
• 10/19: Approximations for the graph diameter
• 10/21: Additive approximations for APSP
• 10/26: Graph spanners
• 10/28: Distance oracles; HW3 due, HW4 out
• 11/1: [paper list is out]
• 11/2: Perfect matching: Rabin-Vazirani algorithm
• 11/4: Perfect matching: Harvey's algorithm
• 11/9: The Baur-Strassen theorem and graph algorithms
• 11/10: [HW4 Due, HW5 Out, deadline to select papers or research project]
• 11/16: Strassen's algorithm, matrix multiplication algorithms and bilinear problems
• 11/18: omega, Direct Sum, Kronecker Product, Border rank
• 11/23: Border Rank, Bini et al, Intro to Schonhage's Theorem; HW5 due
• 11/30: Schonhage's tau theorem and Coppersmith-Winograd.
• 12/1: 1 page summary of project/paper due.