# CS 591 Fall 2016: Iterative Methods for Graphs and Networks

Lectures: M,W 1.00-2.30pmin MCS B31.

Instructor: Prof. Lorenzo Orecchia, MCS 135D. Office hours: TBA

## Announcements

Homework 1 is out! Find it here.

Please sign-up for two sections of scribing on this google-doc

## Homework

 Homework 1 Due: October 12, in class link Homework 2 Due: December 12, in class link

## Course Information

Course Outline: Iterative methods allow us to trade-off precision and running time to produce theoretically sound, fast algorithms for many optimization problems. These methods rely on a very “continuous” interpretation of the problem, incorporating techniques such as steepest-descent and coordinate descent that strongly rely on geometric intuition. In this class, we will turn this perspective on his head and show that iterative methods can be extremely useful in understanding and efficiently solving fundamental combinatorial problems on graphs, a characteristically discrete structure. This has important implications at a time when input graphs may have even billions of nodes and any super-linear running time is practically infeasible.

Tentative Syllabus: The following topics will be covered:

Spectral Graph Theory: Graph Matrices and Graph Eigenvalues, Random Walks, Applications to Clustering

Electrical Circuits as Graphs: Laplacian systems, Preconditioning, Fast Solvers

Iterative Methods in Convex Optimization: Basics of Convex Optimization, Gradient Descent, Coordinate Descent, Application to Graph Problems

Some of the following topics may also be included:

Metric Embeddings

Semidefinite Programming

Matrix Concentration Bounds for Sparsification and Random Graphs

## Course Policies

Prerequisites
While the class will not depend heavily on background material, it will require familiarity with fundamental algorithmic problems and techniques at the level of CS330 or equivalent. A working knowledge of basic linear algebra is also required. Do not hesitate to contact me if you are not sure whether your previous preparation will allow you to benefit from the class.

There will be three components to the workload in this class: scribing, homework and final exam.

Scribing

In most lectures, two students will act as scribes. These students are expected to collaborate to produce high-quality lecture notes in Latex through the collaborative Latex editor overleaf.com. The scribes should submit a final draft of their notes within 5 days of the class. The quality and clarity of the notes will be part of the evaluation. No student will be asked to scribe more than 3 times.

Homework

There will be 3-5 homework assignments. There will be 3 homework assignments. You are encouraged to collaborate on the solution of the homeworks, but you must write up your own answers. If you do collaborate, you must acknowledge your collaborators.

Final Exam

This will be a take-home exam, on which collaboration is not allowed.

In both homeworks and in the exam, you may rely on published or online material, but you must ackowledge your sources.

Evaluation
The grading will roughly work out as follows: Scribing 50%, Homeworks and Final 50%.