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.
Copyright. All Rights Reserved.