Lecturer 
He Sun


Date: 
March 314, and March 2428, 2014 
Place: 
Rotunda of the 3rd floor, Campus E1. 4 
Time: 
24pm, everyday 
Notice 
This Doctoral Privatissima is a block course for three weeks. For more information about Doctoral Privatissima, click
HERE.

Credits  You earn 6 Credit Points (LP). 
Grading  Students who register the course need to read one paper from the list below, and give an about 2hour
presentation with detailed analysis. 
Prerequisites 
Basic knowledge of algorithm design and linear algebra. 
Content 
Spectral Graph Theory studies the matrix representations of graphs, and offers many unexpected and beautiful connections between two apparently
unrelated branches of mathematics: Algebra and Graph Theory. Due to this connection,
various algebraic questions can be reduced to graph problems, and this insights lead to some new techniques in designing graph algorithms.

Topics 
 Graphs and Groups.
 Matrix Theory.
 Cheeger's Inequality.
 Paths, Flows, and Routing.
 Explicit Constructions of Expanders.
 Spectral Graph Theory on Subgraphs.

Schedule 
Date 
Topic 
References 
March 4

Eigenvalues and the Laplacian of a graph

Chapter 1 of Ref. 1

March 5

Isoperimetric problems

Chapter 2 of Ref. 1

March 6

Path, flows, and routing

Chapter 4 of Ref. 1

March 10

Eigenvalues and quasirandomness

Chapter 5 of Ref. 1

March 11

Expanders and explicit constructions

Chapter 6 of Ref. 1, Ref. 2, and My Old Notes

March 12

Eigenvalues of Symmetric Graphs

Chapter 7

March 13

Eigenvalues of subgraphs with boundary conditions

Chapter 8


Papers for Presentation 
 Shayan Oveis Gharan, Luca Trevisan: A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROXRANDOM 2013: 303316.
 James R. Lee, Shayan Oveis Gharan, Luca Trevisan: Multiway Spectral Partitioning and Higherorder Cheeger Inequalities. STOC 2012: 11171130.
 Adam Marcus, Daniel Spielman, and Nikhil Srivastava: Interlacing Families II: Mixed Characteristic Polynomials and the KadisonSinger Problem, 2013.
 Daniel Spielman, and Nikhil Srivastava: Graph Sparsification by Effective Resistances, SIAM Journal on Computing, 40(6), pages 19131926, 2011.
 Anastasios Zouzias: A Matrix Hyperbolic Cosine Algorithm and Applications. ICALP (1) 2012: 846858.

Similar Courses 

Main References 
 [1] Fan Chung: Spectral Graph Theory, American Mathematical Society, 1997. First four chapters can be downloaded via the link.
 [2] Omer Reingold, Salil Vadhan and Avi Wigderson. Entropy Waves, the ZigZag Graph Product, and New ConstantDegree Expanders and Extractors. Annals of Maths. 155:157187, 2002.
