
Spectral Graph Theory and
Algorithmic Applications Instructor: Amin Saberi Time:
Tuesday/Thursday 2:153:30 Location:
McCullough 126 Short DescriptionThe 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, KadisonSinger problem and approximation algorithms for traveling salesman problems. Long descriptionSpectral 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 pseudorandomness, 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 KadisonSinger 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 56 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 gradingParticipating students are expected to register for the course either for grade or pass/fail. Other class attendees should subscribe to our guest email list, msande337spr1415guests@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. PrerequisitesThe 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, matrixtree theorem: lecture notes. á Lectures 2 & 3: random generation of spanning trees, BurtonPemantle theorem: lecture notes. See also Robin PemantleÕs survey on random generation of spanning trees and LyonPeres 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 maxentropy 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 GodsilRoyle, 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 MomkeSvenssonÕ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 KadisonSinger problem: see
Nikhil's Talk,
MSS survey, as well as this blog
post. Homeworksá
Homework 1 due May 10^{th}.
á
Homework 2 due June 10^{th}. ReferencesGodsil & 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. 19131926, 2011. á Joshua Batson, Dan Spielman, and Nikhil Srivastava, TwiceRamanujan Sparsifiers (Sigest), SIAM Review, Vol. 56, Issue 2, pp. 315334, 2014. Real Stable Polynomials and Interlacing Familiesá Adam Marcus, Dan Spielman, and Nikhil Srivastava, Interlacing Families II: Mixed Characteristic Polynomials and the KadisonSinger Problem, to appear in Annals of Mathematics. á
Adam Marcus, Dan Spielman,
and Nikhil Srivastava, Ramanujan Graphs and the Solution
of the KadisonSinger 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), 521567. Traveling Salesman Problemsá Anari, S. Oveis Gharan, EffectiveResistanceReducing Flows, Spectrally Thin Trees, and Asymmetric TSP. See also recent extension of the proof of KadisonSinger 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. 



