CS395T: Spectral Graph Theory (Spring 2025)

Logistics: TTh 2-3:30
GDC 4.516 (ignore the CMA room listed by the registrar)
Unique Number: 51395
Course web page: http://www.cs.utexas.edu/~diz/395T/25/
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: GDC 4.508
Phone: 471-9729
Office Hours: TBD
Course Overview: Spectral graph theory studies how algebraic properties of matrices, most notably eigenvalues and eigenvectors, give information about the combinatorial structure of graphs, such as connectivity. This course will focus on uses of spectral graph theory in theoretical computer science. I'm still preparing the course, but I will draw on a variety of material, including the following books and lecture notes:
Dan Spielman
Luca Trevisan
Salil Vadhan
David Williamson
Prerequisites: Mathematical and computational maturity, plus familiarity with the following topics:
  • Algebra, including vector spaces, eigenvectors/eigenvalues, and finite fields;
  • Discrete Probability, including moments and deviation bounds of Markov, Chebyshev, and Chernoff;
  • Combinatorics, at least basic combinatorics and graph theory;
  • Algorithms, including their analysis and the notion of polynomial time.
Grading (tentative): 90%: Homework
10%: Participation
Last modified: October 10, 2025.