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
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.
Workload for this course:
- Five problem sets, about two weeks apart. For your grade, we will drop your lowest problem set score.
- 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:
- 12/5: Lecture notes for lecture 23 are here
- 11/30: Lecture notes for lecture 22 are here
- First-come first-serve selection of talk times! Check piazza for the link to the google sheets.
- Reminder that your short project reports are due Dec 1.
- 11/23: Lecture notes for lecture 21 are here
- 11/18: Lecture notes for lecture 20 are here
- 11/16: Lecture notes for lecture 19 are here
- 11/10: Problem set 5 is out: here
- Everyone gets a 1 day extension on the problem set and research topic proposal! Now due Thursday.
- 11/9: Lecture notes for lecture 18 are here
- 11/4: Lecture notes for lecture 17 are here
- 11/3: Paper list is out: HERE. Send your choice for the paper you want to read and present for your final presentation, by email to: 6890mit@gmail.com. Deadline: 11/10. Papers will be given on a first come-first serve basis, and will be striken off the list when they have been picked. Instead of a paper presentation, feel free to pick your own research project and email me (at 6890mit@gmail.com) with your choice.
- 11/2: Lecture notes for lecture 16 are here
- 10/28: Problem set 4 is out: here
- 10/28: Lecture notes for lecture 15 are here
- 10/26: Lecture notes for lecture 14 are here
- 10/21: Lecture notes for lecture 13 are here
- 10/19: Lecture notes for lecture 12 are here
- 10/15: Problem set 3 is out: here
- 10/14: Lecture notes for lecture 11 are here
- 10/12: Lecture notes for lecture 10 are here
- 10/6: Lecture notes for lecture 9 are here
- 10/5: Lecture notes for lecture 8 are here
- 9/30: Lecture notes for lecture 7 are here
- 9/28: Problem set 2 is out: here
- 9/28: Lecture notes for lecture 6 are here
- 9/23: Lecture notes for lecture 5 are here
- 9/21: Lecture notes for lecture 4 are here
- 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: Subgraph isomorphism for small patterns
- 10/12: Girth in unweighted graphs; algorithms for even cycles; HW2 due
- 10/14: Approximation algorithms for the girth;
- 10/15: 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/2: Perfect matching: Rabin-Vazirani algorithm
- 11/3: [paper list is out]
- 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.
- 12/2 Coppersmith-Winograd
- 12/7, 12/9: Presentations.