Additive tables and average list recovery
DefinitionNearLogSetCover966_Main_Supplement_Codesp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
Fix a binary basis for the additive group of . For message coordinates and output coordinates, tables specify
Average zero-error list recoverability means that for every family of symbol lists with , at most messages satisfy for every . Injectivity is a separate property; neither property is part of table data. The bit encoding lists all table entries in basis order. No field multiplication is used, so the binary additive-group representation preserves exactly the source operations.
Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_Random
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
/-- Only the additive group of F_(2^s) occurs in these constructions. Coordinates in an
F₂-basis identify it with Vec s; multiplication is never used. -/
abbrev Tables (k s ell : ℕ) := Fin k → Vec s → Fin ell → Vec s
def vectorAt (s a : ℕ) : Vec s := fun j => if a.testBit j.val then 1 else 0
def vectorIndex {s : ℕ} (v : Vec s) : ℕ := ∑ j : Fin s, (v j).val * 2 ^ j.val
def allWords (k s : ℕ) : List (Fin k → Vec s) :=
List.ofFn fun a : Fin (2 ^ (k * s)) => fun i j =>
if a.val.testBit (i.val * s + j.val) then 1 else 0
def additiveCode {k s ell : ℕ} (f : Tables k s ell) (x : Fin k → Vec s) : Fin ell → Vec s :=
fun j => ∑ i : Fin k, f i (x i) j
noncomputable def AverageListRecoverable {k s ell : ℕ}
(C : (Fin k → Vec s) → Fin ell → Vec s) (h : ℝ) (c : ℕ) : Prop :=
∀ Y : Fin ell → Finset (Vec s), ((∑ j : Fin ell, (Y j).card : ℕ) : ℝ) ≤ h →
(Finset.univ.filter fun x => ∀ j, C x j ∈ Y j).card ≤ c
noncomputable def GoodCode {k s ell : ℕ} (f : Tables k s ell) (h : ℝ) (c : ℕ) : Prop :=
Function.Injective (additiveCode f) ∧ AverageListRecoverable (additiveCode f) h c
def tableEncode {k s ell : ℕ} (f : Tables k s ell) : Str :=
unary k ++ unary s ++ unary ell ++
(List.ofFn fun i : Fin k => (List.ofFn fun a : Fin (2^s) =>
(List.ofFn fun j : Fin ell => List.ofFn fun t : Fin s =>
decide (f i (vectorAt s a.val) j t = 1)).flatten).flatten).flatten
noncomputable def codeInput (k s : ℕ) (h : ℝ) : Str := unary k ++ unary s ++ thresholdCode h
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Definition 4.1 and Lemma 4.2, printed p.16 (PDF p.18); Appendix B, printed pp.30–31 (PDF pp.32–33)