Local versus Global Properties of Metric Spaces Extended abstract

Sanjeev Arora, László Lovászt, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala

Research output: Contribution to conferencePaper

10 Scopus citations

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 ℓ 1 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.

Original languageEnglish (US)
Pages41-50
Number of pages10
DOIs
StatePublished - Feb 28 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityMiami, FL
Period1/22/061/24/06

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Local versus Global Properties of Metric Spaces Extended abstract'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., Lovászt, L., Newman, I., Rabani, Y., Rabinovich, Y., & Vempala, S. (2006). Local versus Global Properties of Metric Spaces Extended abstract. 41-50. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States. https://doi.org/10.1145/1109557.1109563