# Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry

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

## Key facts

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

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

- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [On the Fine-Grained Hardness of Inverting Generative Models](https://mlsanity.com/paper/2309.05795/) (2023)
- [A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search](https://mlsanity.com/paper/2609.02143/) (2026)

## Abstract (arXiv)

Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectures. This area has been thriving in the last decade, leading to conditionally best-possible algorithms for a wide variety of problems on graphs, strings, numbers etc. This article is an introduction to fine-grained lower bounds in computational geometry, with a focus on lower bounds for polynomial-time problems based on the Orthogonal Vectors Hypothesis. Specifically, we discuss conditional lower bounds for nearest neighbor search under the Euclidean distance and Fr'echet distance.