# Hardness of Approximate Nearest Neighbor Search

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2018.

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

- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [TPU-KNN: K Nearest Neighbor Search at Peak FLOP/s](https://mlsanity.com/paper/2206.14286/) (2022)
- [Approximate Nearest Neighbor Search with Window Filters](https://mlsanity.com/paper/2402.00943/) (2024)
- [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)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [nSimplex Zen: A Novel Dimensionality Reduction for Euclidean and Hilbert Spaces](https://mlsanity.com/paper/2302.11508/) (2023)
- [On Complexity of 1-Center in Various Metrics](https://mlsanity.com/paper/2112.03222/) (2021)
- [On the Fine-Grained Hardness of Inverting Generative Models](https://mlsanity.com/paper/2309.05795/) (2023)
- [Instance-based learning using the Half-Space Proximal Graph](https://mlsanity.com/paper/2102.02755/) (2021)
- [Faster and Simpler Greedy Algorithm for k-Median and k-Means](https://mlsanity.com/paper/2407.11217/) (2024)
- [Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair](https://mlsanity.com/paper/2508.06774/) (2025)
- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)
- [Efficiently Approximating Attention Is Hard](https://mlsanity.com/paper/2609.37261/) (2026)

## Abstract (arXiv)

We prove conditional near-quadratic running time lower bounds for approximate Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance. Specifically, unless the Strong Exponential Time Hypothesis (SETH) is false, for every δ>0 there exists a constant ε>0 such that computing a (1+ε)-approximation to the Bichromatic Closest Pair requires n2-δ time. In particular, this implies a near-linear query time for Approximate Nearest Neighbor search with polynomial preprocessing time. Our reduction uses the Distributed PCP framework of [ARW'17], but obtains improved efficiency using Algebraic Geometry (AG) codes. Efficient PCPs from AG codes have been constructed in other settings before [BKKMS'16, BCGRS'17], but our construction is the first to yield new hardness results.