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: background, matrix-tree theorem: lecture notes.

á      Lectures 2 & 3:  random generation of spanning trees, Burton-Pemantle theorem: lecture notes. See also Robin PemantleÕs survey on random generation of spanning trees and Lyon-Peres book on probability on trees and networks

á      Lecture 4: traveling salesman problems I: n O(logn/loglogn) approximation algorithm for ATSP: paper by Asadpour et al. on the subject. See also a related result by Singh and Vishnoi on the computation of max-entropy distributions.

á      Lecture 5: graph sparsification I: sampling and via effective resistance: lecture note. See also Spielman and SrivastavaÕs paper.

á      Lecture 6: the interlacing method and applications in combinatorics: Chapter 9 of Godsil-Royle, Haemers Paper on the subject.  

á      Lectures 7, 8, and 9: real stability and hyperbolicity of polynomials: See Pemantle's Survey, VinzantÕs Talk on Hyperbolicity, and VishnoiÕs Survey .

á      Lecture 10: strongly Rayleigh measures and negative association. See Robin Pemantle's Survey as well as Borcea et al.Õs wonderful paper.

á      Lecture 11: traveling salesman problems II: a randomized rounding algorithm for symmetric TSP: see Oveis Gharan et alÕs, result as well as Momke-SvenssonÕs.

á      Lecture 12: graph sparsification II: spectral barriers and linear sparsifiers: see this result by Batson et al.

á      Lectures 12, 13, and 14: proof of the Kadison-Singer problem: see Nikhil's Talk, MSS survey, as well as this blog post.

 

 

Homeworks

á      Homework 1 due May 10th.

á      Homework  2 due June 10th.

References

 

Godsil & RoyleÕs book and LovaszÕs survey are perfect introductions to the subject.

á      Algebraic Graph Theory, by Godsil and Royle.

á      Eigenvalues of Graphs, by Laszlo Lovasz.

 

The following two courses are most similar to ours:

á      Shayan Oveis GharanÕs Recent Developments in Approximation Algorithms (CSE 599), is ongoing in University of Washington with a very similar syllabus and point of view.  Some of our lecture notes borrow heavily from his.

á      Dan SpielmanÕs, Spectral Graph theory, taught in 2012.

 

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.