Friday, September 01, 2006

FOCS 2006

The program of FOCS 2006 is online. According to persistent rumors, the conference will be held in Berkeley.

The program lists Xi Chen (陈 西?) and Xiaotie Deng (邓 小铁?) as winners of the best paper award, for resolving the complexity of the problem of computing Nash equilibria, one of the fundamental (formerly) open questions in computational game theory. Nicholas Harvey receives the best student paper award.

Update (9/4/96): registration is open.

Expander graphs and their applications

A few years ago, Nati Linial and Avi Wigderson taught a course on expander graphs. The course lecture notes have been edited into an article that will appear in the Notices Bulletin of the AMS.

Thursday, August 31, 2006

The Szemeredi Regularity Lemma

This semester I will mostly be securing the cyberspace, but I also plan to learn more about additive combinatorics and its applications to computer science.

In the last few days I have been trying to understand the proof of the Szemeredi Regularity Lemma. It is actually not as hard as I thought.

The Szemeredi Regularity Lemma states that every graph can be approximately described by an object whose size is a constant that depends only on the accuracy of the approximation, and not on the number of vertices of the graph.

This remarkable ``approximate classification theorem for graphs'' has several applications in extremal combinatorics, additive combinatorics, and computer science.

(Indeed, besides such applications, one may imagine using the Regularity Lemma as follows: to prove an approximate quantitative statement about arbitrary graphs, we only need to prove a related statement for the finite set of objects that approximate arbitrary graphs up to a certain level of accuracy. The latter, completely finite, goal may be performed via a computer search. Unfortunately, the size of the objects arising in the Regularity Lemma grow so astronomically fast in the approximation that this approach is completely impractical.)

Roughly speaking, the Lemma says that for every graph G=(V,E) and every parameter eps, we can find a partition of V into equal-size subsets V1,...,Vk such that, for almost all pairs i,j, the edges between Vi and Vj form a dense bipartite "expander." Furthermore, k depends only on eps.

Let us define the notion of "expansion" that we will use. Let G=(U,V,E) be a bipartite graph, where U and V are sets of vertices and E is the set of edges. Let A be a subset of U and B be a subset of V. Define the density d(A.B) of the edges between A and B as e(A,B)/|A|*|B|, that is, the number of edges between A and B divided by the maximum number of possible edges. If G were a random graph, we would expect the density d(A,B) to be approximately the same for all large enough sets A and B, and to always be approximately |E|/|U|*|V|. We say that U and V are eps-regular if for every A of size at least eps*|U| and every B of size at least eps|V| the density d(A,B) is equal to |E|/|U|*|V| plus or minus eps.

Szemeredi Regularity Lemma For every eps there is a constant c(eps) such that for every t and every graph G=(V,E) we can find a partitio of V into at least t and at most t*c(eps) sets of equal size V1...Vk, such that for at least a 1-eps fraction of the pairs i,j, the sets Vi and Vj are eps-regular.

[A minor technical point: the number of vertices of the graph may not be divisible by the number of sets in the partition, so we allow one of the sets in the partition to be slightly smaller than the other k-1 sets.]

The idea of the proof is to start with an arbitrary partition of the sets of vertices into t sets. If the partition satisfies the lemma, we are done. Otherwise, for many pairs Vi,Vj we can find a subset Aij of Vi and a subset Aji of Vj such that both subsets are large but the density of the edges between them is not close to the density of the edges between Vi and Vj. We then refine our partition using these sets. This means that we take every set in the partition and we further subdivide it into subsets (in a way that we describe shortly). The refinement is chosen in such a way that the densities in the new partition are more "disordered" or have more "variance" than they had before. In particular, after the refinement, we show that a function that measures such "disorder" increases by at least poly(eps). Such function can never be more than 1, so we never need to refine the partition more than poly(1/eps) times. At the end, we are left with a partition that satisfies the Lemma and that contains a number of sets that depends only on eps.

It now remains to: (i) define the function that measures disorder; (ii) describe the refinement step; (iii) prove that the refinement increases the disorder function by at least poly(eps).

Let V1,....,Vk be a partition of V, and let pi=|Vi|/|V| be the fraction of elements in Vi. We define the variance of the partition as

f(V1,...,Vk):= sumij pi*pj*(d(Vi,Vj))2

We can interpret this quantity as follows. Consider the random variable X defined by the following experiment: we pick at random, independently, two vertices u,v, we let Vi be the set containing u and Vj be the set containing v, and we define X as d(V_i,V_j). Then f(V1,...,V_k) is the expectation of X2. Also, observe that the expectation of X is simply |E|/|V|2, independent of the partition, and so f(V1,...,Vk) indeed measures, up to additive factors, the variance of X.

It is now an exercise in the use of Cauchy-Schwartz to prove that f() cannot decrease if we refine the partition by splitting a set into two or more subsets.

Now, suppose that Vi and Vj are not an eps-regular pair, and let A and B be subsets witnessing this fact. Split Vi into A,Vi-A and Vj into B,Vj-B. This is now a more "disordered" partition, because the density d(A,B) is noticeably more (or noticeably less) than d(Vi,Vj), and so it also has to be noticeably different from at least one of the three other densities d(A,Vj-B), d(Vi-A,B), d(Vi-A,Vj-B). In fact, we can show that the contribution of the pair Vi,Vj to the variance grows from pipjd2(Vi,Vj) to at least pipjd2(Vi,Vj) + const*pipj*eps4.

If our partition is not eps-regular, then at least an eps fraction of all pairs is not eps-regular, and, by splitting each pair we can increase the variance by at least const*eps5.

There is, however, a difficulty. Let's say that the pair V1 and V2 is not eps-regular, (as witnessed by sets A,B) and neither is V1 and V3 (as witnessed by sets A' and C). What do we do if A and A' are different? Do we split V1 according to A or to A'.

The answer is both, that is, we split V1 into four sets so that A is the union of two of them, and A' is also the union of two of them. In general, if V1 participates into k-1 non-eps-regular pairs, then we split V1 into 2k-1 subsets. For each non-eps-regular pair Vi,Vj, where A,B are the sets witnessing the non-regularity, this refinement is finer than the refinement that simply breaks Vi into A,Vi-A and Vj into B,Vj-B, and so it increases the contribution of Vi,Vj to the variance by at least as much.

This refinement creates subsets of different sizes, while we want the sets to have the same size. We can adjust the size by further refining the large sets and possibly merging small sets, a process that can slightly reduce the variance but, if done properly, by less than half of the amount we gained previously.

Overall, the number of sets in the partition increases exponentially, and the variance increases by at least const*eps5. This means that we reach an eps-regular partition after no more than O(1/eps5) steps. The number of sets in the partition, unfortunately, can now be as large as a tower of exponentials of height O(1/eps5).

Gowers has shown that such towers-of-exponential growth is necessary.

Monday, August 28, 2006

Did all those trees die in vain?

The first computer science section is Saturday afternoon, and it is all about Israeli theory: Omer Reingold and I are speaking, and Avi Wigderson chairs the section. I talk about the complexity-theoretic approach to derandomization and pseudorandomness, and about the coding theory / average-case complexity and the extractors / pseudorandom generators connections. Omer talks about expanders, pseudorandom walks, and L=SL. Here are the slides of my talk. (Based on this paper.)

The attendance is very good, both in quantity and quality, but nobody asks questions after the talk.

Invited speakers are presented with a gift from the organizers. It is an exquisite, two-volume, leather-bound edition of the work of Archimedes. One volume contains a reproduction of the original hand-written ancient Greek. In recognition of the fact that not many people can read ancient Greek, the second volume helpfully contains a Spanish translation.

When I made travel plans for the conference, I assumed that I would start teaching tomorrow. Instead, thanks to a timely approval of my green card, I will spend the semester securing the cyberspace at IPAM, in Los Angeles. So, even though I could have stayed longer, I left on Sunday morning and I am going to miss Ben Green's talk and the rest of the computer science program, not to mention Random-Approx in Barcelona. Between the two-volume Archimedes thing, the two-volume proceedings, and the volume of abstracts, it is a miracle that I am able to close my bag. At the airport, they find my bag to be overweight, and I have to pay 19 Euros.

Here is all the stuff I had to carry: