Local Global Tradeoffs in Metric Embeddings

Konstantin Makarychev
IBM Thomas J. Watson Research Center

Suppose that every k points in an n point metric space X are D-distortion embeddable into L1. We give upper and lower bounds on the distortion required to embed the entire space X into L1. In this setting, we show that X can be embedded into L1 with distortion O(D log (n/k)). Our bounds improve on the results of Arora, Lovasz, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions.

I will mention related geometric questions and state open questions.

Joint work with Moses Charikar and Yury Makarychev.

Back to Long Programs