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

Refresher texts

Supplementary reading


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!

Exams

Instructions

Scribing


Amitabha Bagchi