# 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 ${d: V\times V \rightarrow {\mathbb R}}$ be a semimetric defined over a finite set ${V}$. Then there exists a mapping ${F: V \rightarrow {\mathbb R}^m}$ such that, for every two elements ${u,v \in R}$,

$\displaystyle || F(u) - F(v)||_1 \leq d(u,v) \leq ||F(u)-F(v)||_1 \cdot c\cdot \log |V|$

where ${c}$ is an absolute constant. Given ${d}$, the mapping ${F}$ can be found with high probability in randomized polynomial time in ${|V|}$.

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 ${O(\log n)}$-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 ${\lambda_2}$

Let ${G=(V,E)}$ be an undirected graph with ${n:= | V |}$ vertices.

We define the uniform sparsity of a cut ${(S,V-S)}$ as

$\displaystyle {\sf usc}_G(S) := \frac {E(S,V-S)}{ |S| \cdot |V-S| }$

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

$\displaystyle {\sf usc}(G):= \min_{S} {\sf usc}_G(S)$

In ${d}$-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 ${(S,V-S)}$, we have

$\displaystyle \phi(S,V-S) = \frac {E(S,V-S)}{d \cdot \min \{ |S|, |V-S| \} }$

and, noting that, for every, ${S}$,

$\displaystyle \frac 1n |S| \cdot |V-S| \leq \min \{ |S|, |V-S| \} \leq \frac 2n |S| \cdot |V-S|$

we have, for every ${S}$,

$\displaystyle \phi (S,V-S) \leq \frac nd \cdot {\sf usc}(S) \leq 2 \phi(S,V-S)$

and so

$\displaystyle \phi(G) \leq \frac nd \cdot {\sf usc}(G) \leq 2 \phi(G)$

It will be instructive to see that, in ${d}$-regular graphs, ${\lambda_2}$ is a relaxation of ${\frac nd {\sf usc}(G)}$, a fact that gives an alternative proof of the easy direction ${\lambda_2 \leq 2 \phi(G)}$ 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 ${d: V\times V \rightarrow {\mathbb R}}$ be a semimetric defined over a finite set ${V}$. Then there exists a mapping ${F: V \rightarrow {\mathbb R}^m}$ such that, for every two elements ${u,v \in R}$,

$\displaystyle || F(u) - F(v)||_1 \leq d(u,v) \leq ||F(u)-F(v)||_1 \cdot c\cdot \log |V|$

where ${c}$ is an absolute constant. Given ${d}$, the mapping ${F}$ can be found with high probability in randomized polynomial time in ${|V|}$.

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 ${O(\log n)}$-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.