In this research-oriented graduate course, we will study algorithms for graph partitioning and clustering, constructions of expander graphs, and analysis of random walks.

In this research-oriented graduate course, we will study algorithms for graph partitioning and clustering, constructions of expander graphs, and analysis of random walks. These are three topics that build on the same mathematical background and that have several important connections: for example it is possible to find graph clusters via random walks, and it is possible to use the linear programming approach to graph partitioning as a way to study random walks.


We will study spectral graph theory, which explains how certain combinatorial properties of graphs are related to the eigenvalues and eigenvectors of the adjacency matrix, and we will use it describe and analyze spectral algorithms for graph partitioning and clustering. Spectral graph theory will recur as an important tool in the rest of the course. We we will also discuss other approaches to graph partitioning via linear programming and semidefinite programming. Then we will study constructions of expander graphs, which are graphs with very strong pseudorandomness properties, which are useful in many applications, including in cryptography, in complexity theory, in algorithms and data structures, and in coding theory. Finally, we will study the mixing time of random walks, a problem that comes up in several applications, including the analysis of the convergence time of certain randomized algorithms, such as the Metropolis algorithm.



More info: http://venture-lab.org/expanders


Comments

April 23. Lecture: introduction and basics of spectral graph theory
Homework 1 out, due May 7

May 1. Lecture: Cheeger's inequality and computing eigenvalue and eigenvectors of Cayley graphs

May 8. Lecture: approximately computing eigenvalues and eigenvectors, and more spectral graph theory results
Homework 2 out, due May 22

May 15. Lecture: the Leighton-Rao algorithm and Bourgain's theorem

May 22. Lecture: the Arora-Rao-Vazirani algorithm
Homework 3 out, due June 5

May 29. Lecture: Algebraic constructions of expanders

June 5. Lecture: Combinatorial constructions of expanders, and applications
Homework 4 out, due June 19

June 12. Lecture: Markov Chain Monte Carlo algorithms for approximate counting and optimization

June 19. Lecture: The MCMC algorithm for approximately sampling the matchings of a graph
Peer evaluation of each homework will run during the week following the submission. June 26, the end of peer evaluation of Homework 4, is the end of the class

 

Tell your friends: