The sign layout and the cost bound of the conditional-expectation subroutine
DefinitionDetANN_Supplement_Greedyapproximate-nearest-neighborprogram-verificationreal-ram
Two definitions used by the construction program pre (definition DetANN_Supplement_PreProg).
- , for : for all , the real cell holds . This is the layout written by
preand read by the evaluation programev. - : the step bound of one call of the subroutine
EVALofpre, which evaluates the conditional expectation of Lemma 6.2 for difference vectors in dimension , repetitions and moment order .
Definition code
import Mathlib
import Definitions.Def_DetANN_SignedBlocks
/-!
# Milestone 21 (`DetANN.Supplement.theorem_3_2`): the sign layout and the cost of `EVAL`
`SignsAt mem L k ξ` says that the sign `signOf (ξ ℓ r) ∈ {±1}` is stored in the real cell
`-2^k - 1 - (ℓ·2^k + r)`, the layout written by the construction program `pre` and read by the
evaluation program `ev`. `evalB N d L p₀` is the step bound of one call of the subroutine `EVAL` of
`pre` (the conditional expectation of Lemma 6.2) for `N` difference vectors, dimension `d`, `L`
repetitions and moment order `p₀`.
-/
namespace DetANN.Supplement.Thm32
open DetANN
/-- The signs `ξ` are stored at the real cells `-2^k - 1 - (ℓ·2^k + r)`. -/
def SignsAt (mem : ℤ → ℝ) (L k : ℕ) (ξ : Fin L → Fin (2 ^ k) → Bool) : Prop :=
∀ (ℓ : Fin L) (r : Fin (2 ^ k)), mem (-(2 ^ k : ℤ) - 1 - ((ℓ : ℤ) * 2 ^ k + r)) = signOf (ξ ℓ r)
/-- The step bound of one call of `EVAL`. -/
def evalB (N d L p₀ : ℕ) : ℕ := 100 * (N + 1) * (d + 1) * (L + 1) * (d + 4 * p₀ + 3) ^ 3
end DetANN.Supplement.Thm32
Source
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a proof of DetANN.Supplement.theorem_3_2 (Feng, Indyk, STOC 2027 submission, Theorem 3.2, p.7; the construction of §6.1, p.14, and the conditional expectation of Lemma 6.2). The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.