Optimal (Euclidean) Metric Compression

Piotr Indyk, Tal Wagner

We study the problem of representing all distances between $n$ points in ${\mathbb{R}}^d$, with arbitrarily small distortion, using as few bits as possible. We give asymptotically tig…