[HCS]CS Table 4/9 5:30PM
zeilberg at hcs.harvard.edu
Sun Apr 6 19:07:03 EDT 2003
At CS Table this week, David Xiao will give a talk about expander
graphs, aka "computer scientists' best friends". The talk will
begin after dinner, for which we'll meet in the Eliot House Small
Dining Room at 5:30PM. All are welcome!
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
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