[HCS]CS Table 4/9 5:30PM

[Noam Zeilberger]

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!
---

Expander Graphs

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.