Spectral Graph Theory and Algorithmic Applications

Instructor: Amin Saberi

Time: Tuesday/Thursday 2:15-3:30

Location: McCullough 126

 

Short Description

The course aims to bring the students to the forefront of a very active area of research. We will start by reviewing classic results relating graph expansion and spectra, random walks, random spanning trees, and their electrical network representation. Then, we will cover recent progress on graph sparsification, Kadison-Singer problem and approximation algorithms for traveling salesman problems.

 

Long description

Spectral methods have emerged as a powerful tool with applications in data mining, web search and ranking, computer vision, and scientific computing. They have also become a theoretician's friend in analyzing the mixing times of random walks in graphs, the study of expanders and pseudo-randomness, and graph partitioning.

 

Recently, there has been a lot of exciting developments in spectral graph theory and its applications in algorithm design. For example, consider graph sparsification. Given a dense graph G, is there a weighted sparse graph G' that has the same spectrum (and hence the same cut structure) as G? The study of this question over the past few years has led to a much deeper understanding of graph spectra, faster algorithms for classic problems, a beautiful proof for the Kadison-Singer problem, as well as proof of existence of new families of Ramanujan graphs.

 

One of the most interesting aspects of this line of research is its unexpected connections to the geometry of roots of polynomials and how they can be used to address probabilistic problems. These techniques have also find applications in the analysis of the recent approximation algorithms for traveling salesman problems.

 

The course aims to bring the students to the forefront of a very active area of research. We will start by quickly reviewing classic results relating graph expansion and spectra, random walks, random spanning trees and their electrical network interpretations. However, most of the time will be spent on the development over the past 5-6 years, open problems, and new directions for research.

 

Outline

Graph Expansion and conductance, expander graphs, Cheeger's inequality

Random walks on graphs, mixing times, hitting, commute, and cover times.

Random Spanning trees and their electrical network representation

Thin trees I, O(log(n)/loglog(n)) approximation algorithm for Asymmetric TSP

Graph sparsification I: independent sampling, O(log(n)) sparsifiers for cuts and spectra

Interlacing polynomials I, real stable distributions and their properties

Random spanning trees, new approximation algorithms for TSP

Interlacing polynomials II, Kadison Singer problem

Graph sparsification II: twice Ramanujan sparsifiers

Thin trees II, spectral representation, and polylog(n) integrality gap for ATSP

Free probability, finite convolutions, and Ramanujan graphs

 

Participation and grading

Participating students are expected to register for the course either for grade or pass/fail. Other class attendees should subscribe to our guest e-mail list, msande337-spr1415-guests@lists.stanford.edu via mailman.

 

There will be three problem sets and a research project. Students who are taking the course for pass/fail can skip the projects and one problem set.

 

Prerequisites

The prerequisite for this class is a strong foundation in algorithms, linear algebra, and probability theory at the level of a graduate course.

 

Lectures

      Lecture 1:

 

References

 

Godsil & Royles book and Lovaszs survey are perfect introductions to the subject.

      Algebraic Graph Theory, by Godsil and Royle.

      Eigenvalues of Graphs, by Laszlo Lovasz.

 

We will review the following papers in the class:

Graph Sparsification

      Dan Spielman and Nikhil Srivastava, Graph Sparsification by Effective Resistances, SIAM Journal on Computing, Vol. 40, No. 6, pp. 1913-1926, 2011.

      Joshua Batson, Dan Spielman, and Nikhil Srivastava, Twice-Ramanujan Sparsifiers (Sigest),  SIAM Review, Vol. 56, Issue 2, pp. 315-334, 2014.

 

Real Stable Polynomials and Interlacing Families

      Adam Marcus, Dan Spielman, and Nikhil Srivastava, Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem, to appear in Annals of Mathematics.

      Adam Marcus, Dan Spielman, and Nikhil Srivastava, Ramanujan Graphs and the Solution of the Kadison-Singer Problem, Proceedings of the 2014 International Congress of Mathematicians. 2014.

      Julius Borcea, Petter Branden and Thomas M. Liggett, Negative dependence and the geometry of polynomials. J. American Mathematical Society 22 (2009), 521-567.

 

Traveling Salesman Problems

      Anari, S. Oveis Gharan, Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. See also recent extension of the proof of Kadison-Singer conjecture by Marcus, Spielman, and Srivastava.

      S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem. , FOCS 2011.

      Asadpour, A. Madry, M. Goemans, S. Oveis Gharan, A. Saberi, An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem , SODA 2010.