TIME: 1:30-2:20 pm,  October 9, 2007

PLACE: MGH 295

SPEAKER: Yury Makarychev
         Microsoft Research

TITLE:  Local-Global Tradeoffs in Metric Embeddings


ABSTRACT:
Suppose that every k points in an n point metric space X are D-distortion
embeddable into l_1. We give upper and lower bounds on the distortion
required to embed the entire space X into l_1. This is a natural mathematical
question and is also motivated by the study of relaxations obtained by
lift-and-project methods for graph partitioning problems.

In this setting, we show that X can be embedded into l_1 with distortion
O(D  log (n/k)). Moreover, we give a lower bound showing that this result
is tight if D is bounded away from 1. For D = 1 + delta we give a lower
bound of Omega(log (n/k) / log (1/delta)); and for D=1, we give a lower
bound of Omega(log n/(log k + log log n)). Our bounds improve on the results
of Arora, Lovasz, Newman, Rabani, Rabinovich and Vempala, who initiated
a study of these questions.

Joint work with Moses Charikar and Konstantin Makarychev.