# 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.

# 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.