עופר נימן

A major open problem in the field of metric embedding is the existence of dimension reduction for n-point subsets of Euclidean space, such that both distortion and dimension depend only on the doubling constant of the pointset, and not on its cardinality. In this paper, we negate this possibility for ℓ_p spaces with p > 2. In particular, we introduce an n-point subset of ℓ_p with doubling constant O(1), and demonstrate that any embedding of the set into ℓ_p^d with distortion D must have D ≥ Ω ((c log n/d ^1/2-1/p Copyright is held by the owner/author(s).