The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁

Abstract

In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into ℓ 1 with constant distortion. We show that for an arbitrarily small constant δ > 0, for all large enough n , there is an n -point negative type metric which requires distortion at least (log log n ) 1/6-δ to embed into ℓ 1 . Surprisingly, our construction is inspired by the Unique Games Conjecture (UGC), establishing a previously unsuspected connection between probabilistically checkable proof systems (PCPs) and the theory of metric embeddings. We first prove that the UGC implies a super-constant hardness result for the (nonuniform) S PARSEST C UT problem. Though this hardness result relies on the UGC, we demonstrate, nevertheless, that the corresponding PCP reduction can be used to construct an “integrality gap instance” for S PARSEST C UT . Towards this, we first construct an integrality gap instance for a natural SDP relaxation of U NIQUE G AMES . Then we “simulate” the PCP reduction and “translate” the integrality gap instance of U NIQUE G AMES to an integrality gap instance of S PARSEST C UT . This enables us to prove a (log log n ) 1/6-δ integrality gap for S PARSEST C UT , which is known to be equivalent to the metric embedding lower bound.

Locations

• Journal of the ACM - View
• arXiv (Cornell University) - PDF