Proposition 2.3 — Deterministic CR sparse recovery
ProvedLinearSetReconciliation327.Main.proposition_2_3linear-sketchp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1set-reconciliationsparse-recovery
There are fixed update and decoding programs and constants such that for and there is a fixed binary matrix with at most rows and column weight at most ; a coordinate update of takes at most steps, and from the deterministic decoder recovers every as an explicit support within steps. No random table is used; the expander adjacency lies in the deterministic preprocessed table.
Differences from the source:
- encoding: 0-based or 1-based coordinates [N] → 0-based Fin N or range N, with supports as finite sets and vector addition as symmetric difference; reason: the source identifies subsets with characteristic vectors and any injection relabels the coordinates
- reading: word-RAM with Θ(log n)-bit words, O(1) access to public permutations and inverses, coefficients and precomputed expander tables, preprocessing excluded → one fixed program on a concrete instruction set, width W with clog n ≤ W ≤ cW·log n, uniform permutation and coefficient tables of a TableSpec, and one deterministic seed-independent table of word-address size; reason: §2.1 names the expander adjacency and §§4.2, 5.3, 6.2 precompute parameter-only capacities under the preprocessing exclusion; a fixed program chosen first and a seed-independent table of at most 2^W words exclude free decoders and input or seed advice
- encoding: O-notation with absolute constants → explicit absolute constants and exponents quantified before all instance parameters; reason: §2.1: unless stated otherwise constants are absolute
- encoding: decoder time O(t log(t+2) log(N+2)), which is zero at t=0 → K·max{1, t log(t+2) log(N+2)}; reason: a machine takes at least one step, so this is the same bound with the t=0 convention made explicit
Preamble
import Mathlib import Definitions.Def_LinearSetReconciliation327_Main_Basic import Definitions.Def_LinearSetReconciliation327_Main_WordRAM open scoped ENNReal open Finset
Formal statement
namespace LinearSetReconciliation327.Main
/-- Proposition 2.3 (Deterministic sparse recovery), PDF p.10 (printed p.9). -/
theorem proposition_2_3 :
∃ (progUp progDec : Program) (K cW : ℝ), 0 < K ∧ 0 < cW ∧
∀ N t : ℕ, 1 ≤ N → t ≤ N →
∃ (W R : ℕ) (det : ℕ → ℕ) (H : (Fin N → ZMod 2) →ₗ[ZMod 2] (Fin R → ZMod 2)),
WidthOK W N cW (lg ((N : ℝ) + 2)) ∧ wordsOf W R ≤ 2 ^ W ∧
(R : ℝ) ≤ K * ((t : ℝ) * lg ((N : ℝ) + 2) ^ 2) ∧
ColumnWeightLE H (K * lg ((N : ℝ) + 2) ^ 2) ∧
TogglesWithin progUp (detEnv W det) H (K * lg ((N : ℝ) + 2) ^ 2) ∧
∀ x : Fin N → ZMod 2, (univ.filter fun i => x i = 1).card ≤ t →
∃ s' : RAMState,
HaltsWithin progDec (detEnv W det)
(K * max 1 ((t : ℝ) * lg ((t : ℝ) + 2) * lg ((N : ℝ) + 2)))
(decoderStart W (H x) []) s' ∧
OutputsSupport s' x := by sorry
end LinearSetReconciliation327.Main
Source
Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou, STOC 2027 submission #327 (October 2026), Proposition 2.3, PDF p.10 (printed p.9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.