Polynomial-work RAM computation of the exact matching-vector word length
ProvedITPIRPreproc.MatchVec.WordRAM.wordLengthProgram_correctformal-verificationmatching-vectorsword-ram
Let be a nonnegative integer and let , with . The explicit 35-instruction word-RAM program is deterministic and streaming. Given the self-delimiting encoding of followed by any suffix, it halts with , , and in registers 0, 1, and 2, respectively. It consumes exactly the encoding of , leaves the suffix unread, and writes no output. For every coin tape, it satisfies
This verifies computation of the exact least word-length parameter used by the polynomial matching-vector family, from the standard initial machine state. The work and storage bounds refer to the mission's original word-RAM model. It is one component of the uniform indexed construction; coefficients, coordinate enumeration, and vector output are not asserted by this theorem.
Preamble
import Definitions.Def_ITPIRPreproc_MatchVec_RAMParameters import Definitions.Def_ITPIRPreproc_MatchVec_PolynomialParameters import Mathlib.Tactic open ITPIRPreproc.MatchVec ITPIRPreproc.MatchVec.WordRAM ITPIRPreproc.MatchVec.PolynomialConstruction
Formal statement
theorem ITPIRPreproc.MatchVec.WordRAM.wordLengthProgram_correct :
Deterministic wordLengthProgram ∧ Streaming wordLengthProgram ∧
∀ (h : ℕ) (tail : List Bool) (ω : ℕ → Bool),
Halts wordLengthProgram (encNat h++tail) ω ∧
(finalState wordLengthProgram (encNat h++tail) ω).regs 0=h ∧
(finalState wordLengthProgram (encNat h++tail) ω).regs 1=2^h ∧
(finalState wordLengthProgram (encNat h++tail) ω).regs 2=wordLength h ∧
(finalState wordLengthProgram (encNat h++tail) ω).inPos=(encNat h).length ∧
output wordLengthProgram (encNat h++tail) ω=[] ∧
haltStep wordLengthProgram (encNat h++tail) ω≤50*(h+2)^2 ∧
cost wordLengthProgram (encNat h++tail) ω≤200*(h+2)^4 ∧
workingBits wordLengthProgram (encNat h++tail) ω≤8*((h+2)^2+1) := by sorrySource
Derived implementation lemma for Definitions.Def_ITPIRPreproc_MatchVec_RAMParameters and the least-word-length specification in Definitions.Def_ITPIRPreproc_MatchVec_PolynomialParameters, corresponding to Appendix A of Dujmovic-Lai-Wichs, Nearly Optimal Information-Theoretic PIR with Client Preprocessing, STOC 2027 submission #572. The program and explicit runtime constants are supplied by this formalization.