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 in variables, expressed as a sum of squares of an arbitrary number of linear forms, there is a positive linear combination of at most of these squares which is -close to . 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 point subset of can be embedded with -distorsion in with . Assaf’s Bourbaki report contains a half-page derivation of this result from BSS sparsification. I cannot refrain from reproducing it here.
Express the -induced metric as a combination of cut metrics,
where . Denote by the standard basis of . For every , let
BSS provide us with a collection of at most subsets of , and nonnegative weights , , such that
This means that for every vector ,
Define vectors by
Let . Then . Thus
Substituting into the BBS inequality gives
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. -embeddable metrics are combinations of cut metrics. Newman and Rabinovich generalize metrics (thought of as -dimensional volumes of graphs) to volumes of simplicial complexes. Cuts generalize to coboundaries in -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.