mlsanityData to 14 Oct 2026

Hardness of Approximate Nearest Neighbor Search

arXiv 1803.00904 ↗First posted 2 Mar 2018cs.CC cs.DScited by 19

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 3; 2023: 5; 2024: 5; 2025: 1; 2026: 2.

19 papers.

Sort:

By area:

  1. 2022On The Computational Complexity of Self-Attentioncited by 139
  2. 2023Fast Attention Requires Bounded Entriescited by 102
  3. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  4. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  5. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  6. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  7. 2022TPU-KNN: K Nearest Neighbor Search at Peak FLOP/scited by 18
  8. 2024Approximate Nearest Neighbor Search with Window Filterscited by 11
  9. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  10. 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
  11. 2023The complexity of non-stationary reinforcement learningcited by 7
  12. 2023nSimplex Zen: A Novel Dimensionality Reduction for Euclidean and Hilbert Spacescited by 3
7 more
  1. 2021On Complexity of 1-Center in Various Metricscited by 1
  2. 2023On the Fine-Grained Hardness of Inverting Generative Modelscited by 1
  3. 2021Instance-based learning using the Half-Space Proximal Graphcited by 0
  4. 2024Faster and Simpler Greedy Algorithm for k-Median and k-Meanscited by 0
  5. 2025Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Paircited by 0
  6. 2026Learning Partition Trees for Nearest Neighbor Searchcited by 0
  7. 2026Efficiently Approximating Attention Is Hardcited by 0