Course Information

Announcements

• Take home final: Definition 2 in problem 2 has been reworded to make it more clear. We have post a revised version here: Final-1.
• The Take home final is posted Final. It is due on December 16th at 11:30AM.
• I have added a clarification to problem 7 homework 1.
• There will be no class on Friday October 28. There is a Faculty retreat.
• 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.