Abstract

Expander graphs are extremely useful objects. In computer science, their applications range from network design, computational, 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 focus on the recent combinatorial constructions, via the "zig-zag" product, and how these can go beyond the bounds achieved by algebraic methods. I'll also demonstrate some of the applications.

This talk is accessible to graduate students with no special background in Math and Computer Science.