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

arXiv: https://arxiv.org/abs/1305.4581 · HTML: https://mlsanity.com/paper/1305.4581/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2013.

## Built on by (most cited first, 4 of 4)

- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering](https://mlsanity.com/paper/2406.04857/) (2024)
- [Mathematics of Data Science](https://mlsanity.com/paper/2607.11938/) (2026)
- [Graph Partitioning with Demands: Generalized Conductance and its Applications](https://mlsanity.com/paper/2607.13218/) (2026)

## Abstract (arXiv)

In this paper, 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 (loglog n)1/6-δ to embed into ℓ1. Surprisingly, our construction is inspired by the Unique Games Conjecture (UGC) of Khot, 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 (non-uniform) Sparsest Cut 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 Sparsest Cut. Towards this, we first construct an integrality gap instance for a natural SDP relaxation of Unique Games. Then we "simulate" the PCP reduction and "translate" the integrality gap instance of Unique Games to an integrality gap instance of Sparsest Cut. This enables us to prove a (log log n)1/6-δ integrality gap for Sparsest Cut, which is known to be equivalent to the metric embedding lower bound.