[HCS]CS Table TODAY
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