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

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.

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:

• Basics of convex optimization: gradient descent method, multiplicative weight update method, constrained optimization, interior-point methods
• Elements of spectral graph theory: random walks, graph Laplacians, electrical flows
• Fast algorithms for linear system solving
• Advanced graph algorithmic concepts: sparsification, low-stretch spanning trees, cut-based graph decompositions, oblivious routing

The final project can take several forms:

• Making a theoretical contribution, such as solving an open problem (does not need to be very difficult), bringing a new perspective on an existing theoretical question.
• Writing a (short) survey, based on a few papers, that covers a topic that is related to -- but not really covered in -- the class. (See below for some topics suggestions.)
• Implementing one of the algorithms presented in the class and evaluate its performance in practical scenarios.
• Developing a way to relate one of the concepts covered in the class to your PhD research. This connection should be new and, ideally, not too obvious, but it does not need to lead to any improvements.

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:

• Nesterov's accelerated gradient descent.
• Solving Laplacian systems via coordinate gradient descent/Kaczmarz method.
• Computing matchings with random walks.
• Constructing linear-size spectral sparsifiers.
• Spectral partitioning.
• Generating random spanning trees.

(Talk to Aleksander to get pointers on where to learn about these topics.)

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:

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:

• Thu 9/10: Dimitris T.
• Tue 9/15: NO CLASS (Aleksander is out of town)
• Thu 9/17: Jonathan W.
• Tue 9/22: Tal W.
• Thu 9/24: Jarosław B.
• Tue 9/29: Ehimwenma N.
• Thu 10/1: Christina L.
• Tue 10/6: Mathieu D.
• Thu 10/8: Aleksander M.
• Tue 10/13: NO CLASS (Monday schedule)
• Thu 10/15: Aleksander M.
• Tue 10/20: NO CLASS (FOCS)
• Thu 10/22: Zhenyu L.
• Tue 10/27: Slobodan M.
• Thu 10/29: Amy O.
• Tue 11/3: Mina K.
• Thu 11/5: Jack M.
• Tue 11/10: Guha B.
• Thu 11/12: Devendra S.
• Tue 11/17: Slobodan M.
• Thu 11/19: Francisco U.
• Tue 11/24: Devendra S.
• Thu 11/26: NO CLASS (Thanksgiving)
• Tue 12/1: Aleksander M.
• Thu 12/3: Aleksander M.
• Fri 12/4: Aleksander M.

    Scribing guidelines:

• Make sure to send Aleksander an initial draft of your notes within 24 hours of the lecture you were scribing for. This way: (a) the notes can be disseminated quickly (making all your colleagues happy); (b) preparing the notes while the lecture is still fresh in your mind is easier (making you happy/ier).
• Send a more polished version later. Feel free to schedule a meeting with Aleksander to get feedback on your initial draft. (This is a good opportunity for improving your technical writing skills.) Only the final polished version will be graded.
• The target audience of these notes is you and your colleagues a couple of weeks after the lecture, when you already have forgotten what the lecture was about. Therefore, while scribing the notes you should strive to present, in a succinct, readable, and technically correct (but not too formal) way, all the important points, concepts and results presented in the lecture. A couple of more concrete suggestions:
  • Start by briefly summarizing the main topics discussed in the lecture;
  • Try to use full sentences/prose - avoid bullet points;
  • Make sure to also include the provided motivation, illustrative examples and intuitions related to the presented concepts/algorithms/proofs.
  • If there is a simple figure that you feel would be helpful in understanding something, especially if I drew it during the lecture, try to include it. I recommend LaTeXDraw as a tool for preparing figures in LaTeX, it has a pretty good and expressive GUI and gets the job done quickly.
  • Make sure that all the formal arguments are correct and do not have any gaps in reasoning - if something in the argument is unclear to you, just email Aleksander for clarification.
  • Please spell check your notes and polish the grammar/language.
  (Here is a collection of scribe notes (from a different course) that can serve as an example of the expected style and quality.)

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.