Abstract Lecture 2:

Expander graphs are extremely useful objects. In computer science, their applications range from network design, computational complexity, derandomization, error correction, data organization and more. In mathematics they are used in topology, group theory, game theory, information theory and naturally, graph theory.

I plan to explain what expanders are, their basic properties, and survey the quest to explicitely construct them. I'll survey algebraic constructions, and then focus on more recent combinatorial constructions, via the "zig-zag" product. I'll explain the advantages and disadvantages of each, as well as some interesting connections between them. I'll also demonstrate some of the applications.