Some updates

So far we have seen a few different definitions of expanders (edge expansion, vertex expansion, spectral expansion with second largest or second largest in absolute value eigenvalue), some mixing properties and its applications to reducing the number of random bits used in a BPP algorithm. Kevin presented quantitative connections between the various definitions. Last week we had Erin present the first zig-zag paper. This week David will present the second zig-zag paper on "lossless" (bipartite) expanders.

Coming up are applications of expanders. Some of you have already signed up for some topics. (The sign-up process has been a little ad hoc. The dates below are a little flexible, especially for the last few presentations; if anyone who hasn't signed up for a presentation wants to take one of the following dates -- or topics -- let me know ASAP.)

Oct 5, 7: Mike will present a cryptographic application, of amplifying the hardness of inverting a "one-way function."

Oct 12, 14: Phil will present some results on "extractors," which are devices used for refining "imperfect" sources of randomness to obtain "pure randomness." (We will see some of this in David's presentation, but won't have enough time to do justice to the topic at that point.)

Oct 19, 21: Hemanta will present a log-space algorithm for undirected connectivity in graphs (the celebrated SL=L result).

Oct 26, 28: Reza will present Irit Dinur's proof of the PCP theorem.

That leaves Chris, Nitish and Tracy for November. I'll get you some choices for what to present.