Computer Science/Discrete Mathematics Seminar II

Bi-lipschitz embeddings of finite metric spaces into Hilbert space have become an increasingly important tool in discrete mathematics and theoretical computer science. For example, this theory is intimately related to the algorithmic problem of computing the edge expansion of a combinatorial graph. I will discuss the problem of embedding finite subsets of L_1 into a Hilbert space with minimal distortion of the distances. The most natural question here is whether the L_1 metric on the discrete k-dimensional hypercube is furthest from a Hilbert space amongst all finite subsets of L_1 of the same cardinality. I will show that the answer is essentially yes. A generalization of this theorem (with exactly the same proof) yields the best-known efficient algorithm for approximating edge expansion (and its generalizations) in graphs. The proof breaks down into two parts, corresponding to two distinct classes of obstructions to embeddability. The first involves asymptotic high-dimensional phenomena like graph expansion and concentration of measure. The second part deals with the "non-homogeneity" of arbitrary metric spaces, and how this interacts with properties of Hilbert space like uniform convexity. I will give an overview of the whole proof, and then I'll give a more detailed exposition of the latter part.