6.890 Graph and Matrix Algorithms


Graduate Level
Prereqs: 6.006, 6.046
Instructor: Professor Virginia Vassilevska Williams (virgito@gmail.com)
Schedule: TR1-2:30, room 35-225
This subject will qualify as a Theoretical Computer Science concentration subject.

Due to the surprisingly fast algorithms for the problem, matrix multiplication is routinely used as a basic building block for algorithms beating the brute-force approach. This course explores a variety of problems, mostly within graph algorithms, and discusses how they can be solved faster using a fast matrix multiplication algorithm. We will also see that although many of these problems provably require the use of matrix multiplication to be solved exactly, sometimes matrix multiplication can be avoided by computing answers approximately, leading to very fast algorithms. Finally, we will discuss most of the known algorithms for matrix multiplication including the Coppersmith-Winograd algorithm and its relatives.

Topics include: Graph Transitive Closure, All Pairs Shortest Paths, Perfect Matching, distance oracles, graph spanners, matrix multiplication algorithms, and a variety of equivalences between problems involving matrix multiplication. Prerequisites: 6.046 or the equivalent mathematical maturity.