# Hardness of Approximate Nearest Neighbor Search - Theory
> Explaining the conditional hardness of Approximate Nearest Neighbor (ANN) search based on SETH and innovations like Algebraic Geometry (AG) codes.

Tags: nearest-neighbor, computational-complexity, seth, ag-codes, pcp-theorem, algorithms, theoretical-cs
## Seminar Title: Hardness of Approximate Nearest Neighbor Search
- **Author:** Aviad Rubinstein (Harvard University, 2018)
- **Problem:** Investigates the complexity of Approximate Nearest Neighbor (ANN) and Bichromatic Closest Pair (BCP) search.

## Main Theoretical Results
- **Theorem 1.1:** Assuming SETH, computing a (1+ε)-approximation for BCP in Euclidean, Manhattan, or Hamming space requires nearly quadratic Ω(N²⁻ᵄ) time.
- **Corollary 1.3:** First conditional hardness result for approximate ANN queries, showing that preprocessing in O(Nᶜ) doesn't allow sublinear query time O(N¹⁻ᵄ).

## Key Proof Building Blocks
- **SETH (Strong Exponential Time Hypothesis):** The base hardness assumption regarding k-SAT.
- **Orthogonal Vectors (OVC):** An intermediate problem used for reductions.
- **Distributed PCP:** A framework to avoid gadget blowup in reductions.
- **Algebraic Geometry (AG) Codes:** Replacing Reed-Solomon codes with AG codes provides constant rates, eliminating log-factor overheads and enabling constant-factor hardness gaps.

## MA-Communication Protocol (Theorem 3.1)
- Describes a protocol for Set Disjointness where Merlin (prover) sends a hint to Alice, achieving soundness ≤ 1/2 with minimal communication bits: O(m log T / T).

## Hardness Reduction (Theorem 4.1)
- Reduces Orthogonal Vectors to (1+ε)-approx BCP by embedding the MA-protocol acceptance behavior into vector distances.
- **Result:** Orthogonal pairs result in small distances while non-orthogonal pairs maintain larger distances, separated by the approximation ratio.
---
This presentation was created with [Bobr AI](https://bobr.ai) — an AI presentation generator.