Source-linked AI summary
Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein
TL;DR
The paper asks whether arbitrarily accurate Bichromatic Closest Pair solutions admit subquadratic algorithms and studies hardness for the related Approximate Nearest Neighbor problem. The reduction instantiates the Distributed PCP framework with Algebraic Geometry codes to improve its efficiency. Assuming SETH, for every constant δ > 0 there exists a constant ε = ε(δ) such that (1 + ε)-approximation of Bichromatic Closest Pair has conditional lower bounds in Euclidean, Manhattan, Hamming, and edit distances.
Problem
The paper asks whether arbitrarily accurate Bichromatic Closest Pair solutions admit subquadratic algorithms and studies hardness for the related Approximate Nearest Neighbor problem.
Source: §1 · p. 2Method
The reduction instantiates the Distributed PCP framework with Algebraic Geometry codes to improve its efficiency.
Source: Distributed PCP · pp. 4–5Results
Assuming SETH, for every constant δ > 0 there exists a constant ε = ε(δ) such that (1 + ε)-approximation of Bichromatic Closest Pair has conditional lower bounds in Euclidean, Manhattan, Hamming, and edit distances.
Source: §1 · p. 3Takeaways & Limitations
With polynomial preprocessing, the results imply a near-linear query-time lower bound for (1 + ε)-Approximate Nearest Neighbor search in these distance settings.
Source: §1 · p. 3The note says AG codes easily yield strong results like Theorem 1.1, but do not shave logarithmic factors in a few closely related applications.
Source: §1.3 · p. 7
Abstract
from arXiv · showhide
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 $\delta>0$ there exists a constant $\epsilon>0$ such that computing a $(1+\epsilon)$-approximation to the Bichromatic Closest Pair requires $n^{2-\delta}$ 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.
1 Introduction
The paper proves SETH-based hardness for approximate Bichromatic Closest Pair and derives a near-linear query-time lower bound for Approximate Nearest Neighbor with polynomial preprocessing. It improves the Distributed PCP framework using Algebraic Geometry codes, while identifying limits for looser approximation factors and related applications.
1 Introduction
- Assuming SETH, for every constant δ > 0, Theorem 1.1 gives a constant ε = ε(δ) for approximating Bichromatic Closest Pair within (1 + ε) in Euclidean, Manhattan, or Hamming distance.The paper also reports an analogous hardness result for edit distance; it says the best algorithms are far from matching that hardness.Source: §1 · p. 3
- Polynomial-preprocessing data structures for (1 + ε)-Approximate Nearest Neighbor search face a near-linear query-time lower bound under SETH across Euclidean, Manhattan, Hamming, and edit distances.The result follows from hardness for the offline Bichromatic Closest Pair variant.Source: §1 · pp. 2–3
1.1 Techniques
- The reduction instantiates the Distributed PCP framework with Algebraic Geometry codes to improve its efficiency.This is presented as the first use of AG codes to yield qualitatively new hardness results.Source: §1.1 · p. 3, AG codes · p. 7
Distributed PCP
- Distributed PCPs address PCP blowup by constructing proofs from half-assignments, but the earlier framework’s communication overhead obstructed fine-grained hardness results.Enumerating protocol messages constrains the parameters needed for a useful approximation gap.Source: Distributed PCP · pp. 4–5
AG codes
- AG codes replace Reed-Solomon codes’ Θ(1 / log n) relative rate while retaining useful code properties, allowing constant T in the reduction.The paper attributes the earlier protocol’s O(log n) overhead to the Reed-Solomon rate.Source: AG codes · p. 5
Edit distance
- For edit distance, the reduction replaces each Hamming-instance bit with a short random string to resist low-distance matches created by shifting.The analysis requires care because the behavior of edit distance on random strings is not well understood.Source: Edit distance · p. 5
1.2 Related work
- Earlier AG-code applications built linear-size PCPs or Interactive Oracle Proofs, whereas this work uses AG codes to obtain new hardness results.The paper situates its contribution alongside prior constructions from and.Source: AG codes · p. 7
1.3 Discussion and open problems
- The paper cannot shave logarithmic factors in some related applications, and its discussion identifies barriers to stronger approximation hardness.It highlights unresolved communication-complexity questions and the triangle-inequality barrier for factor-3-or-greater hardness.Source: §1.3 · pp. 7–8, §1.3.1 · p. 10
2 Preliminaries
The preliminaries connect SETH-based hardness to Orthogonal Vectors and introduce AG codes with algebraic and efficiency properties used later.
2.1 Complexity assumptions
- SETH is known to imply the Orthogonal Vectors Conjecture, which asks whether two sets contain a pair with zero inner product.The conjecture supplies a quadratic-time hardness assumption for sets of size N in dimension c log N.Source: §2.1 · pp. 10–11
2.2 AG codes
- AG codewords are multivariate rational functions, and the codes support addition and multiplication with some loss in distance.The construction uses an efficiently decodable family; both codes can be encoded and checked in polynomial time.Source: §2.2 · p. 11
- The AG code family is systematic on a subset of Θ(n) positions and has linearity and polynomial closure under entrywise products.Systematicity permits any assignment on that subset to extend to a codeword.Source: §2.2 · p. 11
3 communication complexity
The section builds MA and AMA protocols for Set Disjointness using codeword checks of aggregated blockwise products. Their communication costs and acceptance guarantees support the later reductions.
3.1 MA communication complexity
- The MA protocol for Set Disjointness uses an algebraic-geometry-code construction over a partition of the universe into T blocks.Alice and Bob restrict their inputs to each block and encode them with the code.Source: §3.1 · pp. 11–12
- The MA protocol uses O(log T · m/T) Merlin bits and T · ⌈log T⌉ Bob bits.The stated communication bound is derived from the encoded aggregate and Bob's blockwise messages.Source: §3.1 · p. 13
- If Alice accepts with probability greater than 1−δC′, the claimed aggregate equals the true codeword and the sets are disjoint.Disjoint inputs are always accepted, while non-disjoint inputs are accepted with probability at most 1/2.Source: §3.1 · pp. 12–13
3.2 AMA communication complexity
- The AMA protocol samples a subset of blocks and has communication of O(m/T) Merlin bits and O(T) Bob bits, using O(log m) coins.A candidate family of sampled subsets reduces the randomness needed to choose the subset.Source: §3.2 · pp. 13, 15
- If Alice accepts with probability greater than 1 − δC′/2, the sets must be disjoint; when disjoint, Alice always accepts.Otherwise, she accepts with probability at most 1/2.Source: §3.2 · pp. 13–14
4 Approximate Closest Pair
The section reduces Orthogonal Vectors to approximate Bichromatic Closest Pair and extends the hardness to edit distance. It also describes random-string gadgets, their derandomization, and an ANN consequence.
4 Approximate Closest Pair
- For every δ, Theorem 4.1 gives an ε for which (1+ε)-approximate Bichromatic Closest Pair in constant-p ℓp metrics is conditionally hard under SETH and OVC.The theorem covers binary vectors of dimension O(log N) and includes Hamming, Manhattan, and Euclidean distance.Source: §4 · p. 15
- Taking a power of the distance reduces Orthogonal Vectors to approximate Bichromatic Closest Pair in ℓp, transferring OVC hardness to the metric problem.The reduction also gives the Hamming result from Manhattan distance for binary entries.Source: §4 · p. 16
4.1 Edit distance
- For edit distance, Theorem 4.2 gives conditional hardness on binary vectors of dimension O(log N log log N).The stated condition is that SETH and OVC are not false.Source: §4.1 · p. 17
- The edit-distance reduction replaces each Hamming bit with a short random string, using identical strings for matching bits and random strings for mismatches.The construction begins with a hard Hamming-distance instance and expands its coordinates into string blocks.Source: §4.1 · p. 17
Analysis
- The analysis bounds edit distance in terms of the original Hamming distance, ruling out substantially better alignments across the constructed blocks.It uses matching-coordinate and mismatching-coordinate contributions to establish the bound.Source: Analysis · pp. 18–19
Derandomizing the construction
- The construction reduces its random-bit use by generating log log N-wise independent strings, which can be enumerated in N^o(1) time.The argument only needs probabilistic control for short contiguous substrings; longer ones are nearly maximally distant from the shorter comparison string.Source: Derandomizing the construction · p. 19
4.1.1 Edit distance between random strings
- Claim 4.3 establishes concentration for edit distance between random strings using McDiarmid’s inequality.The paper also bounds the expected edit distance between an arbitrary string and a uniformly random string.Source: §4.1.1 · p. 20
4.2 Approximate Nearest Neighbor
- Partitioning one Bichromatic Closest Pair set into subsets lets an ANN structure query the subset containing a close-pair endpoint.The passage states that querying that subset with the other endpoint is guaranteed to find a pair approximately as close.Source: §4.2 · pp. 20–21