CS 789 THEORY SEMINAR** **[home]

Speaker:
Anupam Gupta

Affiliation: Carnegie Mellon University

Date: April 11, 2005

Title: __Sparsest
Cut Problems and Embeddings into L _{1}__

We will talk about two problems: (a) that of
finding good embeddings of finite metric spaces into L_{1}, the
"Manhattan" metric and (b) finding cuts in graphs with small conductance. We
will show that the two problems are closely related to each other, and how
recent results for the former give us approximation algorithms for the latter.

As a corollary of our results, we show the following basic fact about metric

spaces: any n-point subset of L_1 can be embedded
into Euclidean space so that the distances are distorted by a multiplicative
factor of *O(log ^{3/4} n)*, thus improving on a previous

The talk is partly based on results with Shuchi Chawla and Harald Raecke, and will be self contained.