6.890: Algorithms for Graphs and Matrices -- Spring 2017
- Instructor: Virginia Vassilevska Williams
- Time: Mondays 1pm--2:30pm, 34-301
- Office Hours: By appointment/email
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. You only need to submit three of these (of your choice)!
- In-class presentation on a topic of interest related to the course, or on your own research!
- (Optional) Create or Edit the scribe notes for a lecture:
we have some lecture notes from a previous incarnation of this course; your job would be to take your own notes during class, fix any typos or inaccuracies in the old notes and
potentially complete them if some new things are covered. In some rare cases we don't have any lecture notes. Here you'd need to write them from scratch.
The original notes were written in LaTeX so that you'd need to modify some LaTeX code. Please submit the fixed-up scribe notes
within a week of the lecture. You will get partial credit for this: (a) if you are editing, the credit should be enough to bump you if you are inbetween grades, and
(b) if you are writing brand new notes, then the credit would be equivalent to half a problem set.
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:
- 4/29 Homework 5 is here, due May 12: [pdf]
- 4/10 Paper List is out: [PAPERS]. Send an email to virgi@mit.edu with your preferences. First come first serve. Each of you will get 20min in class to present the paper that you chose.
- 4/10 Homework 4 is here, due April 24: [pdf]
- 3/18 Homework 3 is here: [pdf]
- 3/1 Lecture 6 notes are here: [pdf]
- 3/1 Lecture 5 notes are here: [pdf]
- 3/1 Homework 2 is here: [pdf]
- 2/22 Lecture 4 notes are here: [pdf]
- 2/22 Lecture 3 notes are here: [pdf]
- 2/22 Lecture 2 notes are here: [pdf]
- 2/15 Homework 1 is here: [pdf]
- 2/8 Lecture 1 notes are here: [pdf]
- 2/1 Look here for fun stuff to happen!
Upcoming topics (the rough plan: subject to change!)
- 2/8: Introduction to matrix multiplication. Equivalences with other linear algebraic operations. Boolean matrix multiplication (BMM) and triangles.
- 2/13: SNOW day
- 2/15: Four-Russians alg. Yu's alg for BMM. [HW1 out]
- 2/20: President's day.
- 2/21: (TUESDAY) Seidel's algorithm for APSP.
- 2/22: Zwick's algorithm for APSP and Hitting set arguments.
- 2/27: Yuster/Zwick's Distance oracle; APSP in node-weighted graphs
- 3/1: All pairs earliest arrivals, bottleneck paths and the dominance product [HW1 due, HW2 out]
- 3/6: Successor and witness matrices; computing actual paths
- 3/8: Equivalences between APSP and other problems (e.g. graph radius and girth)
- 3/13: Girth in unweighted graphs; algorithms for even cycles
- 3/15: Additive approximations for the girth [HW2 due, HW3 out]
- 3/20: Approximations for the graph diameter
- 3/22: Additive approximations for APSP
- 3/27 and 3/29: SPRING BREAK
- 4/3: Graph spanners [HW3 due]
- 4/5: Distance oracles
- 4/10: More graph spanners [HW4 out, paper list out]
- 4/12: Compact routing
- 4/14: [deadline to select papers to present]
- 4/17: BREAK
- 4/19: Perfect matching: Rabin-Vazirani algorithm
- 4/24: Perfect matching: Harvey's algorithm* [HW4 due, HW5 out]
- 4/26: The Baur-Strassen theorem and graph algorithms*
- 5/1: Strassen's algorithm, matrix multiplication algorithms and rank
- 5/3: Border rank, Schonhage's theorem [HW5 due]
- 5/8: Strassen and Coppersmith-Winograd
- 5/10: Coppersmith-Winograd and beyond
- 5/15,5/17: Presentations.