This project will focus on a class of graphs called expanders. These graphs have important applications in areas of theoretical computer science such as complexity theory, error correcting codes, de-randomization, communication networks etc. For a nice introduction to applications see this talk.



There are many classes of graphs which make good expanders (one such example is the family of d-regular graphs). The analysis of expanders involves several branches of mathematics including graph theory, linear algebra and probability theory and others which makes them interesting mathematical objects to study. For theoretical background take a look at the wikipedia page and the the following course notes.