Lecturer


Thomas Sauerwald and He Sun


Time 
Wednesday 1416, first meeting 19.10.2011

Syllabus

PDF

Announcements 
 For the background knowledge on mathematics and complexity theory,
see
Preliminaries
(Nov. 8)
 Problem Set 1 is available. The
deadline is Nov. 25.
 Homework 1 was corrected.
 Problem Set 2 is available. The
deadline is Jan. 11
 Homework 2 was corrected.
 Problem Set 3 is available. The
deadline is Jan. 27.
 Remarks for the final exam is
available, see here.

Room 
024 in the MPI building (E1 4)

Prerequisites 
Basic knowledge of discrete mathematics and linear algebra.
See Preliminaries.

Content

The course studies advanced topics in graph theory and their applications in computer science.
 Algebraic techniques in graph theory
 Spectra of graphs, second eigenvalue of a graph and its relation to combinatorial properties
 Randomized algorithms and Markov chains
 Construction of expander graphs
 Pseudorandomness theory

Credits

You earn 5 Credit Points (LP)

Preliminary
Schedule

No. 
Date

Lecturer 
Topic

Slides/Lecture Notes

Reference

1 
19.10.2011

He 
Introduction

slides 

2 
26.10.2011 
He 
Spectra of Graphs 
Lecture Notes 

3 
02.11.2011 
He 
Expander Mixing Lemma 
Lecture Notes 
[5] 
4 
09.11.2011 
Thomas 
Cheeger's Inequality 
Lecture Notes 

5 
16.11.2011 

No class 


6 
23.11.2011 
Thomas 
Introduction to Markov Chains 
Lecture Notes 

7 
30.11.2011 
Thomas 
Random Walks versus Independent Sampling 
Lecture Notes 

8 
07.12.2011 
Thomas 
Hitting Time and Cover Time of Random Walks 
Lecture Notes 

9 
14.12.2011 
He 
Construction of Expanders 
Lecture Notes 

10 
11.01.2012 
He 
Undirected Connectivity in LogSpace 
Lecture Notes 

11 
18.01.2012 
He 
Pseudorandom Generators 
Lecture Notes 

12 
25.01.2012 
Thomas 
Recap 









Grading 
 The final exam will be held in the last week of
the semester.
 You have to get 40% of the homework for the
admission to the final exam.

Homework 

Similar Classes 

Main References 
 Fan R. K. Chung. Spectral Graph Theory. CBMS
Regional Conference Series in Mathematics, 1997.
 S. Horry, N. Linial, and A. Wigderson. Expander Graphs and Their
Applications. Bulletin of the American Mathematical Society,
43(4):439561, 2006.
 C. Godsil and G. Royle. Algebraic Graph Theory. Graduate Texts in
Mathematics 207, Springer
 D. A. Levin, Y. Peres and E. L. Wilmer. Markov Chains and Mixing
Times. American Mathematical Society, 2008.

Other References 
 R. Impagliazzo, N. Nisn, and A. Wigderson: Pseudorandomness for
network algorithms. In: Proceedings of the 26th STOC, pages 356364, 1994
 L. Lovasz. Random Walks on Graphs: A Survey.
Combinatorics, pages 146, 1993.
 O. Reingold, S. Vadhan, and A. Wigderson: Entropy waves, the ZigZag
product, and new constantdegree expanders. The Annals of Mathematics,
155(1):157187.
 O. Reingold. Undirected STconnectivity in Logspace. Journal of
ACM, 55(4), 2008.
 P. Sarnak. Selberg's Eigenvalue Conjecture. Notices of the AMS.
42(11):12721277, 1995
 J. R. Shewchuck. Ladies and Gentleman, Allow me to Introduce Spectral and Isoperimetric Graph Partitioning. 2011.PDF
