CSE Theory Seminar
Expander Graphs and the Zig Zag Graph Product
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.