Keith Ball on Bourgain’s Legacy in Geometric Functional Analysis

The Bulletin of the AMS has just posted an article by Keith Ball on the legacy of Bourgain’s work on geometric functional analysis.

This beautifully written article talks about results and conjectures that are probably familiar to readers of in theory, but from the perspective of their mathematical motivations and of the bigger picture in which they fit.

CS294 Lecture 10: Bourgain’s Theorem

In which we prove Bourgain’s theorem.

Today we prove the following theorem.

Theorem 1 (Bourgain) Let be a semimetric defined over a finite set . Then there exists a mapping such that, for every two elements ,

where is an absolute constant. Given , the mapping can be found with high probability in randomized polynomial time in .

Together with the results that we proved in the last lecture, this implies that an optimal solution to the Leighton-Rao relaxation can be rounded to an -approximate solution to the sparsest cut problem. This was the best known approximation algorithm for sparsest cut for 15 years, until the Arora-Rao-Vazirani algorithm, which will be our next topic.

CS294 Lecture 9: The Sparsest Cut Problem

In which we introduce the sparsest cut problem and the Leighton-Rao relaxation.

1. The Uniform Sparsest Cut problem, Edge Expansion and

Let be an undirected graph with vertices.

We define the uniform sparsity of a cut as

(we will omit the subscript when clear from the context) and the uniform sparsest cut of a graph is

In -regular graphs, approximating the uniform sparsest cut is equivalent (up to a factor of 2 in the approximation) to approximating the edge expansion, because, for every cut , we have

and, noting that, for every, ,

we have, for every ,

and so

It will be instructive to see that, in -regular graphs, is a relaxation of , a fact that gives an alternative proof of the easy direction of Cheeger’s inequalities.

CS359G Lecture 9: Bourgain’s Embedding

In which we prove that every metric can be embedded into L1 with logarithmic distortion.

Today we prove the following theorem.

Theorem 1 (Bourgain) Let be a semimetric defined over a finite set . Then there exists a mapping such that, for every two elements ,

where is an absolute constant. Given , the mapping can be found with high probability in randomized polynomial time in .

Together with the results that we proved in the last lecture, this implies that an optimal solution to the Leighton-Rao relaxation can be rounded to an -approximate solution to the sparsest cut problem. This was the best known approximation algorithm for sparsest cut for 15 years, until the Arora-Rao-Vazirani algorithm, which will be our next topic.