## About Assaf Naor’s Bourbaki Seminar talk, jan. 22

Well, the week was not quite finished when I published the last post. Indeed, on saturday, Assaf Naor gave a nice Bourbaki talk on Batson, Spielman and Srivastava’s sparsification theorem.

The theorem states that given a nonnegative quadratic form ${Q}$ in ${n}$ variables, expressed as a sum of squares of an arbitrary number of linear forms, there is a positive linear combination of at most ${O(n/\epsilon^2)}$ of these squares which is ${\epsilon}$-close to ${Q}$. Assaf described a few striking applications and even managed to give a glimpse of the proof.

Let me mention one of these numerous applications. It is a recent theorem of Newman and Rabinovich, quoted in Moses Charikar’s talk last week. It states that every ${n}$ point subset of ${L^1}$ can be embedded with ${(1+\epsilon)}$-distorsion in ${\ell_{1}^{N}}$ with ${N=O(n/\epsilon^2)}$. Assaf’s Bourbaki report contains a half-page derivation of this result from BSS sparsification. I cannot refrain from reproducing it here.

Express the ${L^1}$-induced metric as a combination of cut metrics,

$\displaystyle \begin{array}{rcl} |v_i -v_j|_{L^1}=\sum_{E\subseteq[n]}w_{E}|1_E (i) -1_E (j)|, \end{array}$

where ${w_E \geq 0}$. Denote by ${e_1 ,\ldots, e_n}$ the standard basis of ${{\mathbb R}^n}$. For every ${E\subseteq[n]}$, let

$\displaystyle \begin{array}{rcl} x_{E}=\sqrt{w_{E}}\sum_{i\in E}e_{i}\in {\mathbb R}^n. \end{array}$

BSS provide us with a collection ${\sigma\subset 2^{[n]}}$ of at most ${O(n/\epsilon^2)}$ subsets of ${[n]}$, and nonnegative weights ${s_E}$, ${E\in\sigma}$, such that

$\displaystyle \begin{array}{rcl} \sum_{E\subseteq[n]}x_{E}\otimes x_{E}\leq \sum_{E\in\sigma}s_{E}x_{E}\otimes x_{E}\leq (1+\epsilon)\sum_{E\subseteq[n]}x_{E}\otimes x_{E}. \end{array}$

This means that for every vector ${y\in{\mathbb R}^n}$,

$\displaystyle \sum_{E\subseteq[n]}w_{E}(\sum_{i\in E}y_i)^2 \leq \sum_{E\in\sigma}s_{E}w_{E}(\sum_{i\in E}y_i)^2 \leq (1+\epsilon)\sum_{E\subseteq[n]}w_{E}(\sum_{i\in E}y_i)^2 .$

Define ${n}$ vectors ${z_1 ,\ldots,z_n \in{\mathbb R}^{\sigma}}$ by

$\displaystyle \begin{array}{rcl} z_{i}=(s_{E}w_{E}1_{E}(i))_{E\in\sigma}. \end{array}$

Let ${y=e_i -e_j}$. Then ${(\sum_{i\in E}y_i )^2 =|1_E (i) -1_E (j)|}$. Thus

$\displaystyle \begin{array}{rcl} \sum_{E\in\sigma}s_{E}w_{E}(\sum_{i\in E}y_i)^2 = \sum_{E\in\sigma}s_{E}w_{E}|1_E (i) -1_E (j)|=|z_i -z_j|_{\ell_{1}^{\sigma}}. \end{array}$

Substituting ${y}$ into the BBS inequality gives

$\displaystyle \begin{array}{rcl} |v_i -v_j|_{L^1}\leq |z_i -z_j|_{\ell_{1}^{\sigma}}\leq (1+\epsilon)|v_i -v_j|_{L^1} \end{array}$

Newman and Rabinovich’s proof is different. Their paper contains a higher dimensional generalization of the above embedding theorem. Higher dimensional is taken in the following sense. ${L^1}$-embeddable metrics are combinations of cut metrics. Newman and Rabinovich generalize metrics (thought of as ${1}$-dimensional volumes of graphs) to volumes of simplicial complexes. Cuts generalize to coboundaries in ${{\mathbb Z}/2{\mathbb Z}}$-cohomology, and cut metrics have a generalization, cut volumes. This seems to me related to the topic of Nati Linial’s course, which starts tomorrow.