Lemma 3.3, p.7 — deterministic -ANN in with space and query time
ProvedDetANN.lemma_3_3approximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be nonempty with at most points, , and . There is a deterministic data structure that returns a -approximate nearest neighbor in for every query . For an absolute constant its space is , its preprocessing time is , and its query time is .
Precisely: there are deterministic programs and constants , , fixed before the instance, such that for every list of distinct points of and every :
- preprocessing halts within steps;
- preprocessing stores to at most cells;
- every query halts within steps with a -approximate nearest neighbor.
It is the low-dimensional primitive (approximate Voronoi diagrams of Har-Peled) used on every superblock projection.
Formalization Note Machine and data-structure semantics as in DetANN.IsDetANNStructure.
Differences from the source:
- reading: a deterministic data structure (no machine named) → deterministic programs of PNormReg.Machine without coin and rpow, with the layouts of IsDetANNStructure; space = distinct cells stored to by preprocessing; reason: the same machine reading as the goal
- reading: for each Y, δ there is a data structure; O(m), poly, polylog → one pair of programs and constants C > 1, K, C′ for all instances, δ an input; explicit powers with K; reason: the uniform reading is the stronger one; explicit constants are the meaning of the O-notation
- encoding: Y ⊆ ℝ^m nonempty with at most n points → an injective list of N ≥ 1 points, bounds stated with n = N; reason: every bound increases with n, so n = |Y| is the strongest choice and implies the bound for every n ≥ |Y|
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_DetANN_DataStructure
Formal statement
namespace DetANN
/-- **Lemma 3.3** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), p.7).
For a nonempty `Y ⊆ ℝ^m` with at most `n` points (`m ≥ 1`) and `δ ∈ (0, 1/2)` there is a deterministic
data structure returning a `(1 + δ)`-approximate nearest neighbor for every query in `ℝ^m`, with
space `n(C/δ)^{O(m)} polylog(n/δ)`, preprocessing time `poly(n, m)(C/δ)^{O(m)} polylog(n/δ)` and query
time `O(m² log²(n/δ))`, for an absolute constant `C > 1`.
**Formalization Note.** Same machine and data-structure semantics as `DetANN.theorem_1_1`, with input
parameter `δ`. One pair of programs and the constants `C > 1`, `K`, `C'` come before the instance.
`Y` is an injective list of `N ≥ 1` points and the bounds are stated with `n := N`; since every bound
increases with `n`, this is equivalent to "at most `n` points". `poly(n, m) ≤ C'(n + m)^K`,
`(C/δ)^{O(m)} ≤ (C/δ)^{K m}` (`Real.rpow`), `polylog(n/δ) ≤ (log(n/δ))^K`; `log(N/δ) > log 2 > 0` on the
domain. -/
theorem lemma_3_3 :
∃ Pre Qry : PNormReg.Program, DetProgram Pre ∧ DetProgram Qry ∧
∃ C : ℝ, 1 < C ∧ ∃ K C' : ℕ, ∀ m N : ℕ, 1 ≤ m → 1 ≤ N →
∀ Y : Fin N → EuclideanSpace ℝ (Fin m), Function.Injective Y →
∀ δ : ℝ, 0 < δ → δ < 1 / 2 →
IsDetANNStructure Pre Qry Y δ (1 + δ)
((C' : ℝ) * ((N : ℝ) + m) ^ K * (C / δ) ^ ((K : ℝ) * m) * Real.log (N / δ) ^ K)
((C' : ℝ) * N * (C / δ) ^ ((K : ℝ) * m) * Real.log (N / δ) ^ K)
((C' : ℝ) * (m : ℝ) ^ 2 * Real.log (N / δ) ^ 2) := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), Lemma 3.3, p.7 (PDF p.7); proof in Appendix A, p.19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.