## Course Information

**Instructor:** Gary Miller
(Office Hours: Monday 2-3PM and Thursday 2-3PM )

**Teaching Assistant:** TBA (Office Hours: TBA )

**First Class:** Wednesday September 5th
**Place/Time:** GHC 4102, MWF 10:30 - 11:50AM.

**Course Secretary:**
Erin E. Davis
(Office: GHC 7123)

**Official Course Blog will be Piazza:**
cmu-15-859N Piazza

## Announcements

Homework 3 with better problem explanation is
out PDF. It is due in
class on Wednesday December 7.
Homework 3 is out PDF. It is due in class on Wednesday December 7.
Homework 2 is out PDF. It is due in class on Wednesday October 17.
Homework 1 is out PDF. It is due in class on Wednesday October 3.
Note: due to the CSD IC the first class will be on Sept 5.
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.