Local versus global properties of metric spaces

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. VempalaSODA 2006 · OpenReview

Abstract

Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in l1 with low distortion) are determined by the properties of small subspaces. We note connections to similar issues studied already in Ramsey theory, complexity theory (especially PCPs), and property testing. We prove both upper bounds and lower bounds on the distortion of embedding locally constrained metrics into various target spaces.
BibTeX
@inproceedings{arora2006local,
  author = {Sanjeev Arora and László Lovász and Ilan Newman and Yuval Rabani and Yuri Rabinovich and Santosh S. Vempala},
  title = {{Local versus global properties of metric spaces}},
  booktitle = {SODA},
  year = {2006},
  url = {https://openreview.net/forum?id=SaaeHbWSLxrA},
}

Loading related content...

Figure