Abstract
(This paper is an extended abstract) We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into R^d, where d is fixed (and small). For d=1, it was known that approximating the minimum distortion with a factor better than roughly n^{1/12} is NP-hard. From this result we derive inapproximability with factor roughly n^{1/(22d-10)} for every fixed d.
The proof involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala). For d at least 3, we obtain a stronger inapproximability result by a different reduction: one cannot efficiently distinguish between spaces embeddable in R^d with constant distortion from spaces requiring distortion at least n^{c/d}.