CSE Theory Seminar

Expander Graphs and the Zig Zag Graph Product
Gorjan Alagic
3:30pm-4:30pm, January 26, 2005, ITEB 366

Expanders are highly connected graphs with relatively low degree. Their areas of application range from network design to derandomization. Although probabilistic arguments tell us that expanders are everywhere, in practice it is quite difficult to explicitly construct them. The first such construction was given by Margulis in '73.

The subject of this talk is an explicit constant-degree expander family construction due to Reingold, Vadhan and Wigderson, first published in '01. This construction is unique in that it employs a small generating graph which is then enlarged via the new Zig Zag graph product. This process results in larger and larger expanders, while the degree and expansion properties remain unchanged.