Median-threshold block
ProvedDetANN.HPIM.median_blockapproximate-nearest-neighborcomputational-geometrydata-structures
There are a block of fixed length (definition DetANN_HPIMPreBlocks) and a constant such that the following holds in every host program that embeds at .
Assume:
- , and the local points are stored (
LocalPts); - the run starts at , not halted;
- the integer scratch top (pointer ) is .
Then the run reaches without halting, and:
- real register equals the median threshold of (definition
DetANN_HPIMThreshold); - the host registers other than real register are unchanged;
- it writes only integer scratch cells in ;
- its work is at most .
A brute-force implementation suffices: for every candidate pair distance, count a breadth-first component.
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMPreBlocks import Definitions.Def_DetANN_HPIMLayout
Formal statement
namespace DetANN.HPIM
open PNormReg PNormRegLib
/-- **Median-threshold block.** On `n` local points, it sets real register `10` to
`medThreshold pts`. It writes only integer scratch cells `[Z − C(n+1), Z)` (`Z` = pointer `13`),
and its work is at most `C (n+1)^5 (m+1)`. -/
theorem median_block :
∃ blk : ℕ → Program, ∃ L C : ℕ, IsBlock blk L ∧
∀ (off : ℕ) (Q : Program), Embeds Q (blk off) off →
∀ (m n : ℕ) (pts : Fin n → EuclideanSpace ℝ (Fin m)) (s : State),
1 ≤ m → 1 ≤ n → s.core.pc = off → s.halted = false →
LocalPts s (fun i j => pts i j) → s.core.ptrs 13 ≤ 0 →
∃ t, (run Q s detTape t).core.pc = off + L ∧ (run Q s detTape t).halted = false ∧
(run Q s detTape t).core.regs 10 = medThreshold pts ∧
KeepsLow s (run Q s detTape t) [] [10] ∧
WritesOnly Q s t (fun c => c.1 = false ∧
s.core.ptrs 13 - C * (n + 1) ≤ c.2 ∧ c.2 < s.core.ptrs 13) ∧
(run Q s detTape t).work ≤ s.work + C * (n + 1) ^ 5 * (m + 1) := by sorry
end DetANN.HPIMSource
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a floor-free proof of DetANN.lemma_3_3 (Feng, Indyk, STOC 2027 submission, Lemma 3.3, p.7): the preprocessing program of DetANN.HPIM.hpim_preprocessing is assembled from these blocks. The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.