CS 789 THEORY SEMINAR [home]
Speaker:
Anupam Gupta
Affiliation: Carnegie Mellon University
Date: April 11, 2005
Title: Sparsest
Cut Problems and Embeddings into L1
We will talk about two problems: (a) that of finding good embeddings of finite metric spaces into L1, 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(log3/4 n), thus improving on a previous O(log n) bound of Bourgain (1986).
The talk is partly based on results with Shuchi Chawla and Harald Raecke, and will be self contained.