# On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2018.

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

- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Finding Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2110.06163/) (2021)

## Abstract (arXiv)

Given a set of n points in mathbb Rd, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the ℓp-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when d=ω(log n) was raised as an open question in recent works (Abboud-Rubinstein-Williams [FOCS'17], Williams [SODA'18], David-Karthik-Laekhanukit [SoCG'18]). In this paper, we show that for every p∈mathbb R≥ 1cup0, under the Strong Exponential Time Hypothesis (SETH), for every varepsilon>0, the following holds: bullet No algorithm running in time O(n2-varepsilon) can solve the Closest Pair problem in d=(log n)^Omegavarepsilon(1) dimensions in the ℓp-metric. bullet There exists δ = δ(varepsilon)>0 and c = c(varepsilon)≥ 1 such that no algorithm running in time O(n1.5-varepsilon) can approximate Closest Pair problem to a factor of (1+δ) in d≥ clog n dimensions in the ℓp-metric. At the heart of all our proofs is the construction of a dense bipartite graph with low contact dimension, i.e., we construct a balanced bipartite graph on n vertices with n2-varepsilon edges whose vertices can be realized as points in a (log n)Omega_varepsilon(1)-dimensional Euclidean space such that every pair of vertices which have an edge in the graph are at distance exactly 1 and every other pair of vertices are at distance greater than 1. This graph construction is inspired by the construction of locally dense codes introduced by Dumer-Miccancio-Sudan [IEEE Trans. Inf. Theory'03].