Interfaces for the top-level reduction of Theorem 1.1: structures with a general answer property, and local answers
DefinitionDetANN_Thm11_Splitapproximate-nearest-neighborprogram-verificationreal-ram
Two definitions for splitting Theorem 1.1 into a machine part and a mathematical part.
-
is exactly
IsDetANNStructure(definitionDetANN_DataStructure) with the answer condition "the answer is a -approximate nearest neighbor of " replaced by an arbitrary predicate . The machine, input and query layouts, the time measure (work) and the space measure (distinct cells stored to) are the same. -
for holds when there are candidates , one for each tuple of the walk family , such that:
- they satisfy the local guarantee (25) with for the blocks , the padded point set and the padded query: for all and all in the padded set, ;
- for every .
By
theorem_1_1_correctness, a local answer is a -approximate nearest neighbor whenever is large enough.
Definition code
import Mathlib
import Definitions.Def_PNormReg_Machine
import Definitions.Def_DetANN_DataStructure
import Definitions.Def_DetANN_Construction
import Definitions.Def_DetANN_TupleFamily
namespace DetANN
namespace Thm11
/-!
# Interfaces for the top-level reduction of Theorem 1.1
Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), §7.4, p.19.
The data structure of Theorem 1.1 runs one Lemma 3.3 structure per tuple `v` on the superblock
projections `𝒜_v P` and answers with the best of the `d′ = 2^k` candidates. The reduction separates
the machine part (building and querying these structures) from the mathematics (the local guarantee
implies a `(1 + ε)`-approximate answer, `theorem_1_1_correctness`).
-/
/-- `IsDetANNStructure` with an arbitrary answer property `Ans q k` in place of
"`k` is a `c`-approximate nearest neighbor of `q`". Same machine, layouts and cost measures. -/
def IsDetStructure (Pre Qry : PNormReg.Program) {N m : ℕ} (Y : Fin N → EuclideanSpace ℝ (Fin m))
(θ : ℝ) (Ans : EuclideanSpace ℝ (Fin m) → Fin N → Prop) (Tpre Space Tq : ℝ) : Prop :=
∃ t : ℕ,
(PNormReg.run Pre (inputState Y θ) detTape t).halted = true ∧
((PNormReg.run Pre (inputState Y θ) detTape t).work : ℝ) ≤ Tpre ∧
((cellsWritten Pre (inputState Y θ) t).card : ℝ) ≤ Space ∧
∀ q : EuclideanSpace ℝ (Fin m), ∃ t' : ℕ,
(PNormReg.run Qry (queryState m (PNormReg.run Pre (inputState Y θ) detTape t) q)
detTape t').halted = true ∧
((PNormReg.run Qry (queryState m (PNormReg.run Pre (inputState Y θ) detTape t) q)
detTape t').work : ℝ) ≤ Tq ∧
∃ k : Fin N,
(PNormReg.run Qry (queryState m (PNormReg.run Pre (inputState Y θ) detTape t) q)
detTape t').core.ptrs 0 = (k : ℤ) ∧ Ans q k
/-- The answer `a` of the composed structure: there are candidates `x_v` (one per tuple `v` of the
walk family on `Fin (2^k)`) satisfying the local guarantee (25) with `α = 1 + ε/100` for the blocks
`annBlocks C₀ k P ε`, and `a` is at least as close to `q` as every candidate. -/
def LocalAnswer {d n : ℕ} (C₀ : ℝ) (k : ℕ) (P : Fin n → EuclideanSpace ℝ (Fin d)) (ε : ℝ)
(q : EuclideanSpace ℝ (Fin d)) (a : Fin n) : Prop :=
∃ x : Fin (2 ^ k) → Fin n,
LocalGuarantee (annBlocks C₀ k P ε) (annTuples k ε) (paddedSet k P) (padVec (2 ^ k) q)
(fun v => padVec (2 ^ k) (P (x v))) (1 + ε / 100) ∧
∀ v, ‖q - P a‖ ≤ ‖q - P (x v)‖
end Thm11
end DetANN
Source
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as the top-level reduction of DetANN.theorem_1_1 (Feng, Indyk, STOC 2027 submission, Theorem 1.1, p.2; the construction of §7.4, p.19). The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.