Expander Graphs and the Zig Zag Graph Product

Gorjan Alagic

3:30pm-4:30pm, January 26, 2005, ITEB 366

Gorjan Alagic

3:30pm-4:30pm, January 26, 2005, ITEB 366

Abstract

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.