Course Information

Announcements

• Homework 5 is out and due on Dec 6th.

  For problem 2 the book MarkovChains-MixingTimes will be useful.

• Due to popular demand Homework 4 is now due Monday Nov 18th.
• Homework 4 is out and due on Nov 15th.
• If you did not get asked to join Piazza let Gary or Euiwoong know.
• Homework 3: Hints add to problems 1 and 2.
• Homework 3: corrected the definition of expansion in problem 1
• Homework 3 is out and due on Oct 25th.
• Clarifications have been added to homework 2.
• Welcome to Spectral Graph Theory. Please take a minute to review the course policies.

Overview

At a very high level the course shows how one can use linear algebra to solve fundamental problems in computer science much more efficiently. Many of the problems that these approaches apply to are graph problems such as graph cut and the maximum flow problems, giving almost linear time algorithms. The opposite is also true, we will use graph algorithms to solve problems in linear algebra. This interplay is what will give us these very fast algorithms. The key to these new algorithms is the use of numerical analysis and methods, iterative algorithms. There was a major revolution in algorithms for linear programming in the 1980's and 1990's, which at a high level, can be attributed to the use of Newton's iterative method to find a good approximation to the linear program. Over the last two decades computer scientists starting with Vaidya have introduced the use of Conjugate Gradient and Chebyshev iterations to solve problems such as maximum flow. In the last few months advances have been made using Nesterov iterations. Critical to these new methods are new graph algorithms. One key idea is that of graph sparsification, given a graph and find a new graph with substantially fewer edges that is similar to the original one. In turn finding these sparse graphs uses the design of new types of spanning trees. We two we will discuss are low stretch trees and Bartal Steiner trees.

This class will cover material from three areas: Spectral Graph Theory, Numerical Linear Algebra, and the application to problem in CS.

The central issue in spectral graph theory is understanding, estimating, and finding eigenvectors and eigenvalues of graphs. The study of random walks on a graph was one of the first users of spectral graph theory. Answering such questions as: How many times should you shuffle a deck of cards to insure that the deck is "well shuffled"? More recent application include Google's page rank algorithm which performs a random walk on the hyperlink graph of the Internet. It has also been applied to the problem of finding these eigenvectors as well as solving related linear systems.