Algorithms and Complexity Seminar

Thursday, February 14, 2008, 4:00-5:15pm in 32-G575.

On the Computational Near-Optimality of Random Projection

Anastasios Sidiropoulos (MIT CSAIL)

We consider the problem of computing a minimum-distortion embedding of a finite metric space into a low-dimensional Euclidean space. It has been shown by Matousek [Mat90] that for any d\geq 1, any n-point metric can be embedded into R^d with distortion ~O(n^{2/d}) via a random projection, and that in the worst case this bound is essentially optimal. This clearly also implies an ~O(n^{2/d})-approximation algorithm for minimizing the distortion. We show that for any fixed d\geq 2, there is no polynomial-time algorithm for embedding into R^d, with approximation ratio better than Omega(n^{1/(17d)}), unless P=NP. Our result establishes that random projection is not too far, concerning the dependence on d, from the best possible approximation algorithm for this problem.

Our proof uses a result from Combinatorial Topology due to Sarkaria, that characterises the embeddability of a simplicial complex in terms of the chromatic number of a certain Kneser graph.

The talk will be self-contained.

Joink work with Jiri Matousek

Host: Ning Xie

(The Algorithms and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)