(27), p.18 — for any tuple family with
ProvedDetANN.eq_27approximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Throughout, a tuple family is a map on finite nonempty sets (tuples) and (occurrences) with uniform block frequencies: every block occurs times among the pairs . Choose uniformly and put . For answers and a point write , , , , and for the superblock of (repeated blocks counted with multiplicity). The local guarantee with factor is for every .
Let be a -balanced block system for with , let the answers satisfy the local guarantee with factor , let , and let satisfy . Then
and therefore some tuple has at most the same bound.
With from Lemma 7.2 this is (27) for the walk family; with from Lemma 5.1 it is Theorem 4.1 for the exhaustive family.
Differences from the source:
- generalization: the walk family of §7 (and, in §5, the exhaustive family [d]^s); x⋆ a nearest neighbor of q → any finite tuple family with uniform block frequencies and nonempty Vtx, Occ; x⋆ any point of P; reason: §7.3 says the arguments use only uniform block frequencies and balance of differences; both families have uniform frequencies, and a nearest neighbor is a point of P
- encoding: expectations over the random choice of V and of an occurrence; the min-form local guarantee (11)/(25) → finite uniform averages over Vtx × Occ; the squared guarantee ‖𝒜_v(q − x_v)‖² ≤ α²‖𝒜_v(q − y)‖² for all y ∈ P; reason: the averages are the expectations; for α ≥ 0 and finite nonempty P the squared and min forms are equivalent
- generalization: κ = ρ²/(1 − ρ²) via Lemma 7.2 → any κ ≥ 0 with E_I‖a_I − a‖² ≤ κ𝒱 as a hypothesis; reason: Lemma 7.2 supplies the hypothesis with κ = ρ²/(1 − ρ²), which gives the printed (27)
Preamble
import Mathlib import Definitions.Def_DetANN_BalancedBlocks import Definitions.Def_DetANN_TupleFamily
Formal statement
namespace DetANN
/-- **(27), in the general form** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), §7.3, p.18).
Let `A₁, …, A_d` be a `τ`-balanced block system for `P`, let the answers `x_v ∈ P` satisfy the local
guarantee with factor `α ≥ 1`, let `x⋆ ∈ P` and `r = ‖q − x⋆‖`, and suppose
`E_I ‖a_I − a‖² ≤ κ 𝒱` with `κ ≥ 0`. Then
`√(E_V ‖q − x_V‖²) ≤ (α + √(2α²κ + 12τ(1 + α)²))/√(1 − τ) · r`, and some tuple `v` has
`‖q − x_v‖` at most the same bound.
The paper's (27) is the case `κ = ρ²/(1 − ρ²)` (Lemma 7.2); Theorem 4.1 is the case `κ = 1/(s − 1)`
(Lemma 5.1).
**Formalization Note.** The family is any finite family of tuples `S : Vtx → Occ → Fin d` with
uniform block frequencies and nonempty `Vtx`, `Occ` (the paper: the exhaustive family `[d]^s` of §5
and the walk family of §7). Expectations are finite averages over `(V, O)` uniform on `Vtx × Occ`
(see `DetANN.TupleFamily`). `x⋆` is any point of `P`; the paper takes a nearest neighbor of `q`, and
the argument uses only `x⋆ ∈ P`. -/
theorem eq_27 {d b : ℕ} {Vtx Occ : Type} [Fintype Vtx] [Fintype Occ] [Nonempty Vtx] [Nonempty Occ]
(τ α : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) (hα : 1 ≤ α)
(P : Finset (EuclideanSpace ℝ (Fin d)))
(A : Fin d → EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin b))
(hA : IsBalancedBlockSystem τ P A)
(S : Vtx → Occ → Fin d) (hS : UniformFreq S)
(q xs : EuclideanSpace ℝ (Fin d)) (hxs : xs ∈ P)
(x : Vtx → EuclideanSpace ℝ (Fin d)) (hx : ∀ v, x v ∈ P)
(hloc : LocalGuarantee A S P q x α)
(κ : ℝ) (hκ : 0 ≤ κ) (hκV : betweenVar S x xs ≤ κ * withinVar S x xs) :
Real.sqrt ((Fintype.card Vtx : ℝ)⁻¹ * ∑ v, ‖q - x v‖ ^ 2) ≤
(α + Real.sqrt (2 * α ^ 2 * κ + 12 * τ * (1 + α) ^ 2)) / Real.sqrt (1 - τ) * ‖q - xs‖ ∧
∃ v : Vtx, ‖q - x v‖ ≤
(α + Real.sqrt (2 * α ^ 2 * κ + 12 * τ * (1 + α) ^ 2)) / Real.sqrt (1 - τ) * ‖q - xs‖ := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), (27), §7.3, p.18 (PDF p.18); exhaustive case: Theorem 4.1, p.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.