6.S978 Graphs, Linear Algebra, and Optimization -- Fall 2015

Instructor: Aleksander Mądry (madry@mit.edu), 32-G666
Office hours: Fridays 11-12
Time and place: Tuesdays and Thursdays 2:30-4 pm in 24-307
Units: 3-0-9 (H level)
Class mailing list: http://lists.csail.mit.edu/mailman/listinfo/6s978 (Attention: MIT's anti-spam system likes to junk the signup confirmation request emails.)
The formal prerequisite are fairly minimal: linear algebra (e.g., 18.06), basic algorithms (6.006, but 6.046 recommended), and fundamentals of probability theory (e.g. 6.041 or 18.600). However, this is a graduate-level class and thus it will move fairly quickly. In particular, a considerable mathematical maturity will be needed.

Course description

This course will provide a tour through the ideas and techniques that underlie the emerging theme of developing fast graph algorithms via convex optimization and linear algebra methods. The main focus will be on presenting how these ideas and techniques unfold in the context of fundamental graph problems, such as the maximum flow problem. However, we will also explore connections to certain core questions in convex optimization.

The list of topics that we will touch upon along the way includes:

Announcements: Problem sets: All solutions should be emailed to Aleksander as a PDF file (typeset in LaTeX). Projects

The final project can take several forms:

The project can be prepared either individually or in a group of up to three people. Naturally, a group project should be proportionally larger. While working on your project, you can consult any source or person, just make sure to acknowledge it.

Project proposal: Prepare a one-page project proposal that discusses, in a clear manner, the topic you chose and email it to Aleksander by November 20, 2015. Feel free to consult Aleksander when choosing the topic.

Final project: Please submit the final project write-up by December 20, 2015. The write-up should be up to five pages long. Keep in mind that the quality of presentation is as important as the write-up's scientific content.

Some survey topic suggestions: (Talk to Aleksander to get pointers on where to learn about these topics.)


Grading: The grade will be based on (probably, 2-3) problem sets, scribe notes (each student should do her/his fair share) and a final project (description to be posted shortly). Class participation (e.g., interaction during the lecture, asking good questions) can also (positively) influence your grade.

Scribe notes: There should be one scribe in charge of taking detailed notes during each lecture and then typing them in LaTeX. These notes will be posted on the course website.
LaTeX is a typesetting language in which most (if not all) scientific literature is written. So, if you are not familiar with it yet, it is probably a good time to do it now.
To start, take a look at www.latex-project.org and play with our template.
Instructions regarding signing up for scribing are here,
  1. To reserve a slot, email Aleksander (madry@mit.edu) with your top three preferences among the slots that are still shown as available below.
  2. Signup early so as to get the date that accommodates your individual constraints best. Making later changes will still be possible provided you let Aleksander know at least 48 hours in advance of the date you originally committed to.
    Scribing schedule:
the general scribing guidelines are here (please read them carefully!), and the template is here.
    Scribing guidelines:

Collaboration policy
The final project can (and probably should) be done in teams of two people. In case of problem sets, collaboration with one other person is also allowed, but: (1) the writeup of all the solutions has to be prepared independently (in particular, you should understand and be able to explain everything that is written in your solution); (2) in your writeup, you should include the name of your collaborator.