An Excursion into the World of Expanders

Expander graphs are sparse graphs with strong connectivity properties. This deceptively simple combination of properties has proven to have remarkable implications in computer science. In this course we shall sample some of the fascinating results in this area.

Broadly the topics on expanders can be classified into three: (a) mathematical properties, especially those relating expansion to spectral properties of the graph, (b) constructions of expanders, both combinatorial and algebraic, and (c) applications and connections of expanders to other objects/problems of interest in computer science.

Applications of expanders are numerous and breathtaking. This fast growing list includes:

The exact topics to cover in the course will be decided based on student interest. Each student will be expected to read and present at least one paper. There will be no exams, assignments or scribing. However, students will be encouraged to write short notes at wikipedia.org on topics covered in class. We shall also maintain a blog related to the course. Grading will be based on the presentations and participation in the course (in the classroom and virtually).