CSL863: Special Topics in Theoretical Computer Science
Topic: Expander graphs their applications
II semester: 2014-15
Amitabha Bagchi
Class Timings: Mon Thu 5PM to 6:30PM.
Room: SIT Seminar Room (Ground Floor).
Topics
Topics: Graph expansion and eigenvalues, the Expander
Mixing Lemma, random walks on expander graphs, expander constructions
of Margulis and Gabber-Galil, the spectral gap of expander graphs,
metric embeddings, error correcting codes, and advanced topics based
on interest.
Background required: graph theory, linear algebra.
Texts
- We will loosely follow Nati Linial and Avi Wigderson's course notes. Download here.
Refresher texts
- Linear algrebra can be refreshed from Andrei Antonenko's course notes. Available here.
- Group theory can be reviewed from Jim Howie's lecture notes. Available here.
Supplementary reading
- The proof of the Perron-Frobenius theorem presented in class is from Chapter 9 of the book Dynamical Systems by Shlomo Sternberg (2010, Dover Publications, ISBN-13: 978-0486477053). The entire book can be downloaded at this link.
- The relationship of expansion and the spectral gap to mixing times in random walks on graphs will largely rely on the treatment in the book Markov Chains and Mixing Times by David A. Levin, Yuval Peres and Elizabeth L. Wilmer (2009, AMS, ISBN-13: 978-0-8218-4739-8). The entire book can be downloaded at this link.
- The treatment of Fourier analysis for finding eigenvalues and for proving the expansion properties of some expander constructions will be based on Luca Trevisan's lecture notes from the course CS359G: Graph Partitioning and Expanders, 2011.
List of topics covered
Since the topics covered in the lectures are from a variety of sources, not always following Linial and Wigderson's notes very closely, we list below the topics covered for reference.
Key: LW: Linial and Wigderson's notes; LPW: Levin, Peres and Wilmer's book; AA: Antonenko's notes; SS: Sternberg's book; LT: Luca Trevisan's lecture notes; YLN: Your lecture notes!
- January. Topics included in Minor 1.
- Three applications of expanders: randomness amplification for BPP, superconcentrators and error correcting codes (LW Chap 1).
- Linear algebra revised: Vectors spaces, matrices, operators, eigenvalues and eigenvectors (AA).
- Perron-Frobenius theorem with proof for the irreducible and primitive cases (SS Chap 9).
- February. Topics included in Minor 2.
- Edge expansion, Expander Mixing Lemma, deterministic amplification in BPP, lower bound on spectral gap (LW Chap 2).
- Markov chains, irreducibility and aperiodicity (LPW Chap 1.3), random walks on graphs (LPW Chap 1.4), stationary distribution (LPW Chap 1.5), existence of stationary distribution (using PF theorem, YLN, alternate proof in LPW Chap 1.5.3).
- Total variation distance (LPW Chap 4.1), Convergence theorem for Markov Chains (algebraic proof, YLN, alternate proof in LPW Chap 4.3).
- Mixing time for Markov chains (LPW Chap 4.4, 4.5), lower bound on mixing time using bottleneck ratio (LPW Chap 7.2).
- Spectral representation of a reversible transition matrix (LPW Chap 12.1).
- March. Topics included in Minor 3.
- The relaxation time of a reversible transition matrix, upper and lower bounds on mixing time in terms of relaxation time (LPW Chap 12.2).
- The Dirichlet form and the bottleneck ratio, bottleneck ratio-based upper and lower bounds on spectral gap, i.e. Cheeger's inequality (LPW Chap 13.3).
Additional reading: Please read lectures 2, 3 and 4 of LT for a nice "algorithmic" view of the Cheeger inequality proof.
- A random walk on an expander yields a series of "good samples", applications of expander walks to hardness of approximation (LW Chap 3).
- An algorithm for finding low conductance sets based on Lovasz and Simonovits' theorem (Scribe notes by Dravyansh Sharma and Sai Praneeth).
- April.
- Characters of a group (LT Lec 5).
- Cayley Graphs and their spectrum, the cycle and the hypercube as tight examples for Cheeger's inequality (LT Lect 6).
- Expander constructions, a logarithmic degree expander construction, intro to the zig-zag product construction (LT Lec 16).
- Proof of the spectral property of the zig-zag product (LT Lec 17).
Exams
Instructions
- Handwritten solutions are not allowed. Please do not ask for
exceptions.
- Please save the template in a latex file called
"minor<minor number>-your-name.tex".
- Fill in your answers and your name at the
appropriate places indicated, and, when you are done, printout the pdf
made from this latex file.
- Bring it with you to class on the due date.
- If for some reason you cannot come to class that
day, please drop the exam in my box before the beginning of
class on the due date.
- You are not allowed to refer to the Internet or other
resources except where explicitly indicated.
- You may discuss the solutions with other students but must write
your own solutions.
- A comprehensive resource for latex may be accessed here.
Scribing
- Each student will be expected to scribe notes of the lectures on
Spielman and Teng's algorithm for finding low conductance sets based
on Lovasz and Simonovits' theorem.
- Due Date: In class on Monday, 13 April 2015.
- Please download the template file and the
latex class file that will be needed.
- Apart from your class notes you may also look up the material
covered in class on
the internet. The sources I have used are:
- D. A. Spielman and S.-H. Teng, A
Local Clustering Algorithm for Massive Graphs and Its Application to
Nearly Linear Time Graph Partitioning, SIAM J. Comput.,
42(1):1-26. (You will need an IIT IP address to download the pdf).
- R. Rajaraman. Lecture notes dated 3rd February 2012, from
the class CS 7880: Network Algorithms and Analysis taught at
Northeastern University.
- D. A. Spielman. Chap 7 of Fast, randomized
algorithms for partitioning, sparsification, and the solution of
linear systems. Lecture notes from IPCO Summer School, 2005.
- J. Kelner. Section 3 of Lecture
7, dated 27 September 2007, of the course 18.409: An
Algorithmist's Toolkit taught at
MIT. Scribe: Jose Soto.
- Here are some general
guidelines which may help you with scribing class notes. Please
read them before you begin typing.
Amitabha
Bagchi