6.5350: Matrix Multiplication and Graph Algorithms -- Spring 2026

Time: Tuesdays and Thursdays 11am--12:30pm, 4-163

Instructor: Virginia Vassilevska Williams

TA: John Kuszmaul

Problem Set submission: gradescope: sign up access code will be given during the first lecture or by email if you miss the lecture

Piazza: Sign up here (for the access code, come to the first lecture or email the instructor if you miss it)

Office Hours: John: TBA, Virginia: by appointment

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.

• Five problem sets, about two weeks apart. Each is worth 5% of your grade, 25% altogether.
• In-class presentation on a research paper related to the course, or on your own research. (worth 35% of your grade)
• For your research project: ~1 page project proposal: if you are reading a paper (or papers), a summary of the main contributions of the paper, and if you are proposing a research problem to work on, background, motivation and a description of your initial approach. (worth 5% of your grade)
• A ~5 page long final report on your research project. (worth 35% of your grade)
• You may not use AI (chat gpt and the like) on any part of the workload. You can work with a partner on the research project and problem sets, as long as you specify who that is and as long as you do your own write-up.

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.122 (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.

• 2/1: Look here for fun stuff to happen!

• 2/3: Lecture notes for Lecture 1 are posted on piazza

• 2/3: Introduction to matrix multiplication. Equivalences with other linear algebraic operations. Boolean matrix multiplication (BMM).
• 2/5: Seidel's algorithm for APSP. [HW1 out]
• 2/10: Zwick's algorithm for APSP and Hitting set arguments.
• 2/12: Yuster/Zwick's Distance oracle and application
• 2/17: NO CLASS
• 2/19: All pairs earliest arrivals, bottleneck paths and the dominance product [HW1 due, HW2 out]
• 2/24: Successor and witness matrices; computing actual paths
• 2/26: Subgraph isomorphism for small patterns
• 3/3: Minimum Weight Triangles, Equivalences between APSP and other problems (e.g. graph radius)
• 3/5: Girth in unweighted graphs; algorithms for even cycles [HW2 due, HW 3 out]
• 3/10: Approximation algorithms for the girth
• 3/12: Approximation algorithms for graph diameter
• 3/17: Additive approximations for APSP
• 3/19: Graph Spanners [HW3 due, HW 4 out]
• 3/24,3/26: NO CLASS (spring break)
• 3/31: Distance oracles
• 4/2: Perfect matching: Rabin-Vazirani algorithm
• 4/7: Perfect matching: Harvey's algorithm [paper list is out 4/9]
• 4/9: The Baur-Strassen theorem and graph algorithms [HW 4 due, HW5 out]
• 4/14: Strassen's algorithm, matrix multiplication algorithms and bilinear problems
• 4/16: omega, Direct Sum, Kronecker Product, Border rank [project proposal due: deadline to select papers or research project]
• 4/21: Border Rank, Bini et al, Intro to Schonhage's Theorem;
• 4/23: Schonhage's tau theorem and Coppersmith-Winograd. [HW5 due]
• 4/28,4/30: Finish Coppersmith-Winograd.
• 4/30: project report due.
• 5/5,5/7,5/12: Presentations.