Topic: Expander graphs their applications

Background required: graph theory, linear algebra.

- We will loosely follow Nati Linial and Avi Wigderson's course notes. Download here.

- 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.

- 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.

**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).

- Three applications of expanders: randomness amplification for BPP, superconcentrators and error correcting codes (LW Chap 1).
**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).

- Edge expansion, Expander Mixing Lemma, deterministic amplification in BPP, lower bound on spectral gap (LW Chap 2).
**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).

- Minor 1. Download
tex template here (local access only). Posted 26th January
2015.
**Due: 5th February 2015**.

- Minor 2. Download
tex template here (local access only). Posted 25th February
2015.
**Due: 9th March 2015**.

- Minor 3. Download
tex template here (local access only). Posted 5th April
2015.
**Due: 16th April 2015**.

- 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.

- 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.

- D. A. Spielman and S.-H. Teng, A
Local Clustering Algorithm for Massive Graphs and Its Application to
Nearly Linear Time Graph Partitioning,
- Here are some general
guidelines which may help you with scribing class notes. Please
read them before you begin typing.

Amitabha Bagchi