Objective

This course will focus on research topics in modern algorithm design, including tools, techniques, and their applications to the design of algorithms for fundamental problems in theoretical computer science. In this offering, the focus will be on studying properties of graphs, and designing algorithms for graph problems using numerical algorithms, and methods from continuous optimization and analysis.

Logistics

Where: SS 2101
When: M 3-5pm
Instructor: Sushant Sachdeva
Office hours: By appointment (email me, or catch me after class)

Prerequisites

A good understanding of undergraduate algorithms, Linear algebra, probability, and some vector calculus. Most of all, this course will assume good mathematical maturity as the course will be theoretical and mathematical in nature.

Syllabus

Here is a tentative list of topics we plan to cover in the course:
* Basic spectral graph theory -- eigenvalues and eigenvectors of matrices associated with graphs
* Conductance and connection to random walks
* Cheeger's inequality
* Matrix concentration bounds
* Sparsification using leverage scores / effective resistances
* Solving linear systems in graph Laplacians
* Optimization problems on graph, such as maximum-flow, using continuous methods
In the remaining part of the course, the students will read and present research papers related to the above topics.

Several of these lectures are based on the courses on Spectral Graph Theory taught by Daniel Spielman. (2015, 2018).

Notes

Click on the topic for scribe notes and additional readings. Please note that the scribe notes likely contain typographical errors. I request you to please send me an email with the errors you notice.

  1. 10 Sep
    [Notes] Scribe: Dmitry Paramonov
    In this lecture, we set up our basic notation for graphs, and defined basic matrices related to them. We defined basic spectral theorems, and studied a few spectral properties of simple families of graphs.

    Readings: Sec 2.1 from Lecture 2 of Dan's 2018 course (PDF)
    Optional: solve the problems at the end of these notes.

  2. 17 Sep
    [Notes] Scribe: Liwen Lu
    In this lecture, we explored eigenvalues and eigenvectors of simple graphs using a Julia notebook, and used eigenvectors for spectral graph drawing of simple graphs. We then proceeded to look at the minimum conductance problem, stated Cheeger's inequality and proved the easy direction.

    Julia notebook (as html) borrowed heavily from Dan Spielman's notebook available here)
    Download Julia. If you use a mac, I highly recommend using homebrew.

  3. 24 Sep
    [Notes] Scribe: Muhammed Tahsin Rahman
    In this lecture, we completed the proof of Cheeger's inequality, and started exploring random walks on undirected graphs.

  4. 01 Oct
    [Notes] Scribe: Junwei Su
    In this lecture, we continued discussing random walks on undirected graphs, how the probability distribution evolves over steps, and the rate of convergence of a random walk in terms of the eigenvalues of the normalized Laplacian.

  5. 15 Oct
    [Notes] Scribe: Sara Tang
    In this lecture, we discussed proving the lower bounds on \(\nu_2\), the second eigenvalue of the normalized Laplacian, which allows us to prove tight bounds on the convergence of laze random walks. In the second half, we discussed a little bit of expander graphs.

  6. 22 Oct
    [Notes] Scribe: Calum MacRury
    In this lecture, we considered electrical flows on graphs, and connected the commute time in the graph to the effective resistance between the vertices.

  7. 29 Oct
    [Notes] Scribe: Fengwei Sun
    In this lecture, we started with scalar Chernoff bounds, and then moved to Matrix chernoff bounds, applying them to prove that a collection of \(\log n\) random matchings gives an expander with high probability.

  8. 12 Nov
    [Notes] Scribe: Kevan Hollbach
    In this lecture, we discussed spectral graph sparsifiers, and how they generalize expanders. We then presented a construction of spectral sparsifiers using random sampling based on the paper of Spielman and Srivastava.

  9. 19 Nov
    [Notes1] Scribe: Yasamansadat Mahadaviyeh
    26 Nov
    [Notes2] Scribe: Maxim Goukhshtein
    In this lecture, we discussed fast solvers for Laplacian systems based on approximate Gaussian elimination. We defined and studied some basic properties of schur complements and Cholesky factorization (Gaussian elimination), what does an approximate Cholesky factorization mean, and presenting the algorithm from (Kyng-Sachdeva FOCS 2016) that gives a fast algorithm for approximate Gaussian elimination on Laplacians.

Principle readings

There will be no textbook for the course, but we will use several online resources as reading material, in addition to the scribe notes. Some of the relevant courses/resources are:
* Spectral Graph Theory (2015, 2018), by Daniel Spielman
* Spectral Algorithms by Richard Peng