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.

Next presentations

I forgot to mention this in the class today.

After Kevin presents the connections between spectrum
and expansion, the next topic I'd like to see covered
is some constructions of expanders.

If you read Sariel's recent blog entry you would have
noticed something about zig-zag products. So we need
*two* volunteers to find out if they are indeed related
to clothing as Sariel claims. Two, because there are
two papers on zig-zag products:

Reingold, Vadhan and Wigderson (2000) and
Capalbo, Reingold, Vadhan and Wigderson (2002)

Both are very beautiful papers, and also contain lot of
intuition that will be of use to us later on.

Please send me a mail if you think your life wouldn't
be complete without presenting one of these papers! On
Friday, we'll finalize who's presenting which one.

Eigenlectures

In the last two lectures we covered some very basic linear algebra we'll use to study expanders. We chose our topics mostly following Lecture 2 from the Linial-Wigderson course. Restricting to undirected graphs makes the linear algebra involved very simple (and beautiful, I must say) for us. Some of the things we saw are:

• A graph G defines a linear transform, namely multiplication by its adjacency matrix A. This transform naturally corresponds to how a probability distribution on the nodes of the graph gets transformed in a single step of the (natural) random walk defined on G. (But now that we have a linear transform in our hands, we need not restrict ourselves to applying it to probability distributions. Any real vector is fair game.)


• We'll consider undirected graphs. Then the adjacency matrix A is symmetric (and of course real). Then it can be shown¹ that A=P^TDP, where D is a diagonal matrix and P is an orthonormal matrix (all real). In plain English that means, in some (orthonormal) basis (defined by the rows of P), A is a transformation which simply scales each dimension independently. This change of basis is extremely useful (as we saw in the proof of the "Expander Mixing Lemma").


• Rows of P are "eigenvectors" of A, with corresponding "eigenvalues" being the diagonal entries of D.² Most of what we talked in the class about real symmetric matrices becomes fairly intuitive once we look at D instead of A. One of those intuitive things is the characterization of the spectrum using Rayleigh quotients. Since a Rayleigh quotient is defined geometrically (using angles, lengths etc., with no reference to any particular basis), and the same is true for eigenvalues, it is all right to think of D instead of A.


• Writing A=P^TDP is the same as the "spectral decomposition," A=Σλ_iP_i. Here λ_i is the i-th diagonal entry of D and P_i=v_iv_i^T is the linear transformation which returns the component along v_i, the i-th row of P.


• For d-regular (connected, non-bipartite) graphs, we saw that λ₀ = d, and |λ_i|<d for i>0.


• We analyzed the eigenvalues and eigenvectors of our favorite examples, the clique (with self-loops) and the cycle. The clique has a single non-zero eigenvalue (=n). Then we saw that any d-regular graph has a d/n "component" of the clique in it. An ideal expander would behave as if it didn't have any othercomponents.


• We also saw some relations between the spectral gap and the expansion of a graph. Kevin will talk more about this the week after the next.

______

^1. The proof mentioned above uses induction and is simple, but is not quite "elementary," because it refers to the existence of at least one real eigenvalue for A. The short proof for that depends on the Fundamental Theorem of Algebra, which I'm sure everyone considers second nature, but I don't think is quite what an elementary proof for the above statement should contain. So, if anyone out there can give (pointers to) a simple(r) proof for the spectral decomposition theorem, but restricted to real symmetric matrices, that would be great.

^2. The concept of eigenvalues/eigenvectors is not restricted to linear transforms defined by real symmetric matrices. A typical linear algebraic exposition would first introduce you to eigenvalues/eigenvectors for general linear transforms and then specialize it to real symmetric matrices. To keep our focus, and to keep things simple, we started directly with real symmetric matrices. But beware that the nice behavior described above does not hold in general.

ps: I'm having some very strange problems with the way Firefox is rendering things in my newly acquired powerbook (OS X 10.4). I hope things show up nicely in your browsers... update: fixed it!