|
Lecturer
|
|
Thomas Sauerwald and He Sun
|
|
|
Time |
Wednesday 14-16, 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 Log-Space |
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):439-561, 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 356-364, 1994
- L. Lovasz. Random Walks on Graphs: A Survey.
Combinatorics, pages 1-46, 1993.
- O. Reingold, S. Vadhan, and A. Wigderson: Entropy waves, the Zig-Zag
product, and new constant-degree expanders. The Annals of Mathematics,
155(1):157-187.
- O. Reingold. Undirected ST-connectivity in Log-space. Journal of
ACM, 55(4), 2008.
- P. Sarnak. Selberg's Eigenvalue Conjecture. Notices of the AMS.
42(11):1272-1277, 1995
- J. R. Shewchuck. Ladies and Gentleman, Allow me to Introduce Spectral and Isoperimetric Graph Partitioning. 2011.PDF
|
