Readings

Readings on Spectral Graph Theory

Andersen, R., F. Chung, K. Lang. "Local Graph Partitioning using PageRank Vectors" in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 475-486. Washington, DC: IEEE, October 21-24, 2006.

This is the conference version of Andesen, Chung, and Lang paper on local cutting with PageRank vectors. There is also a longer journal version.

Dan Spielman's Notes on Lovasz-Simonovits Theorem

Notes from Dan Spielman's course on Spectral Graph Theory about the Lovasz-Simonovits theorem. (PDF) (Courtesy of Dan Spielman. Used with permission.)

Jerrum, M., and A. Sinclaire. "Approximating the Permanent." SIAM Journal on Computing 18 (1989): 1149-1178.

This is the original Jerrum-Sinclair paper on approximating the permanent. I looked for a nice textbook writeup or set of lecture notes for the result, but this paper is so beautifully written that I think it's still the best place to read about the result. We'll only cover pp. 1149-1160 (in the journal's page numbers).

Buy at Amazon Motwani, Rajeev, and Prabhakar Raghavan. Randomized Algorithms. Cambridge, UK: Cambridge University Press, 1995. ISBN: 9780521474658.
See section 11.3. This is the section of Motwani and Raghavan's book "Randomized Algorithms." that covers approximating the permanent.

Dan Spielman's Example Computations

These are notes from a lecture given in another class that covered spectral graph theory. In them, many of the examples from today's class (including the grid graph and graph products) are worked out in detail. (PDF) (Courtesy of Dan Spielman. Used with permission.)

Dan Spielman's Notes on Cutting

These are Dan Spielman's notes on using graph spectra for cutting (PDF) (Courtesy of Dan Spielman. Used with permission.)

Chung, F. Chapter 1 in "Eigenvalues and the Laplacian of a Graph." Spectral Graph Theory. (This resource may not render correctly in a screen reader.PDF)

———. Chapter 2 in "Isoperimetric Problems." Spectral Graph Theory. (This resource may not render correctly in a screen reader.PDF)

———. Chapter 3 in "Diameters and Eigenvalues." Spectral Graph Theory. (This resource may not render correctly in a screen reader.PDF)

———. Chapter 4 in "Paths, Flows and Routing." Spectral Graph Theory. (This resource may not render correctly in a screen reader.PDF)

———. "Bibliography." Spectral Graph Theory. (This resource may not render correctly in a screen reader.PDF)

Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs

This is the Benczur-Karger paper that contains the details about how to sparsify graphs for cut problems.

Readings on Iterative Methods for Linear Algebra

Shewchuk, J. "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain." (This resource may not render correctly in a screen reader.PDF)

Readings on Convex Geometry

Ball, K. "An Elementary Introduction to Modern Convex Geometry." (This resource may not render correctly in a screen reader.PDF)

Lovasz, L., and M. Simonovits. "The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume." Foundations of Computer Science 1 (1990): 346-354.

This contains the details of the relative Isoperimetric Inequality.