Lemma 6.2: the conditional expectation of the potential
ProvedDetANN.lemma_6_2approximate-nearest-neighbordata-structuresderandomizationexpander-graphs
Let , let be a real matrix, , and finite, and let be the potential (24) of the signed blocks built from . For every partial assignment of the signs,
where the left side is the average of over all completions and the right side is the explicit generating-function formula of the definition DetANN_SignChoice.
The right side is a finite combination of truncated polynomial products, which is what the algorithm evaluates. So this is the statement that the deterministic sign selection computes the conditional expectation exactly.
Preamble
import Mathlib import Definitions.Def_DetANN_SignedBlocks import Definitions.Def_DetANN_SignChoice
Formal statement
namespace DetANN
/-- **Lemma 6.2.** For every partial assignment `(μ, u)` of the `Ld` signs, the conditional
expectation of the potential `Φ` of (24) equals the explicit generating-function expression
`lemma62Expr`. -/
theorem lemma_6_2 {d : ℕ} (hd : 1 ≤ d) (h : Matrix (Fin d) (Fin d) ℝ) (L : ℕ) (hL : 1 ≤ L)
(τ : ℝ) (p₀ : ℕ) (D : Finset (EuclideanSpace ℝ (Fin d))) (μ u : Fin L → Fin d → Bool) :
condPotential h L τ p₀ D μ u = lemma62Expr h L τ p₀ D μ u := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), Lemma 6.2 and its proof, pp.15–16