The explicit construction of Theorem 1.1 (§7.4)
DefinitionDetANN_Constructionapproximate-nearest-neighbordata-structuresderandomizationexpander-graphs
Fix points , an integer , and a constant .
- Padding. appends zeros (and drops coordinates if ). The padded point set is , and .
- Parameters. as in (12), and .
- Blocks. The signed blocks of §6.1 built from the Sylvester–Hadamard matrix (definition
DetANN_Sylvester) with the greedy signs of the definitionDetANN_SignChoice, scored by the Lemma 6.2 expression. - Tuples. The walk length of §7.4, and the tuples of endpoints of all length- walks from in the Lemma 7.1 graph on .
These are the data structure's blocks and tuples whose correctness is the content of §7.4.
Definition code
import Mathlib
import Definitions.Def_DetANN_SignedBlocks
import Definitions.Def_DetANN_SignChoice
import Definitions.Def_DetANN_Sylvester
import Definitions.Def_DetANN_Multigraph
import Definitions.Def_DetANN_MGG
namespace DetANN
/-!
# The explicit construction of Theorem 1.1 (§7.4)
Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), §7.4, p.19, with §6 for the blocks and §7.1 for the
tuples. The dimension is padded to a power of two `2^k ≥ d`.
-/
/-- Pad `x ∈ ℝ^d` with zeros to a vector of `ℝ^m`. -/
noncomputable def padVec {d : ℕ} (m : ℕ) (x : EuclideanSpace ℝ (Fin d)) : EuclideanSpace ℝ (Fin m) :=
WithLp.toLp 2 fun r => if h : (r : ℕ) < d then x.ofLp ⟨r, h⟩ else 0
/-- The padded point set `{pad(P i)}` in `ℝ^{2^k}`. -/
noncomputable def paddedSet {d n : ℕ} (k : ℕ) (P : Fin n → EuclideanSpace ℝ (Fin d)) :
Finset (EuclideanSpace ℝ (Fin (2 ^ k))) :=
Finset.univ.image fun i => padVec (2 ^ k) (P i)
/-- The differences `pad(P i) − pad(P j)` for `i < j`. -/
noncomputable def diffSet {d n : ℕ} (k : ℕ) (P : Fin n → EuclideanSpace ℝ (Fin d)) :
Finset (EuclideanSpace ℝ (Fin (2 ^ k))) :=
((Finset.univ : Finset (Fin n × Fin n)).filter fun p => p.1 < p.2).image
fun p => padVec (2 ^ k) (P p.1) - padVec (2 ^ k) (P p.2)
/-- The balance parameter `τ = ε²/10⁶` of (12). -/
noncomputable def annTau (ε : ℝ) : ℝ := ε ^ 2 / 10 ^ 6
/-- The number of repetitions `L = ⌈C₀ τ⁻² p₀⌉` with `p₀ = ⌈log₄(8Nd)⌉`, `N = |𝒟|`, `d = 2^k`. -/
noncomputable def annReps {d n : ℕ} (C₀ : ℝ) (k : ℕ) (P : Fin n → EuclideanSpace ℝ (Fin d))
(ε : ℝ) : ℕ :=
numReps C₀ (annTau ε) (momentOrder (diffSet k P).card (2 ^ k))
/-- The blocks of Theorem 3.2 for the padded points: Sylvester matrix, signs chosen greedily by the
Lemma 6.2 expression. -/
noncomputable def annBlocks {d n : ℕ} (C₀ : ℝ) (k : ℕ) (P : Fin n → EuclideanSpace ℝ (Fin d))
(ε : ℝ) (j : Fin (2 ^ k)) :
EuclideanSpace ℝ (Fin (2 ^ k)) →ₗ[ℝ] EuclideanSpace ℝ (Fin (annReps C₀ k P ε)) :=
signedBlocks (sylvester k) (annReps C₀ k P ε)
(greedySigns (lemma62Expr (sylvester k) (annReps C₀ k P ε) (annTau ε)
(momentOrder (diffSet k P).card (2 ^ k)) (diffSet k P)) (annReps C₀ k P ε * 2 ^ k)) j
/-- The walk length `ℓ = ⌈log_{1/θ₀}(200/ε)⌉` of §7.4. -/
noncomputable def walkLen (ε : ℝ) : ℕ := ⌈Real.logb (1 / theta0) (200 / ε)⌉₊
/-- The tuples of §7.1: endpoints of all length-`ℓ` walks in the Lemma 7.1 graph on `Fin (2^k)`. -/
noncomputable def annTuples (k : ℕ) (ε : ℝ) : Fin (2 ^ k) → (Fin (walkLen ε) → Fin 16) → Fin (2 ^ k) :=
walkEnd (lemma71Nbr k) (walkLen ε)
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), §7.4, p.19, with (12), p.9, §6.1, p.14 and §7.1, p.17