Noam Zeilberger zeilberg at hcs.harvard.edu
Wed Apr 9 12:22:12 EDT 2003

Just a reminder that CS Table meets today at 5:30 in the Eliot House
Small Dining Room at 5:30PM.

Expander Graphs (David Xiao)

Graph theory is useful!  Sound suspicious?  OK, how about this: graph 
theory is cool!  Actually, despite what your preconceptions may be, 
both are true, especially in the realm of extremal graph theory.  In 
particular, graphs that have good expansion are both interesting to 
work with and are useful in important situations in theoretical, and 
sometimes even applied, computer science.

Expansion is a difficult notion to pin down, but intuitively a graph is 
a good expander if it is highly connected.  One may think of this 
combinatorially, where every set of vertices is connected to a larger 
set of vertices.  One may also think of this probabilistically, where 
taking a random walk on the graph converges to the uniform distribution 
very quickly.  In fact, it turns out that these two formulations are 
equivalent (roughly)!

In this talk, we'll discuss graphs with good expansion.  We'll quantify 
this notion of expansion a little more concretely, then talk about how 
to build good expander graphs, and finally discuss some areas where 
expansion is useful, focusing on issues in derandomization.

More information about the HCS-Announce mailing list